5x5数字网格中的广度优先和深度优先搜索算法-Java 学习之路

我们应该在一个带有5x5数字网格的文本文件中读取并编写广度优先搜索和深度优先搜索方法 .

我不是要求任何人为我做功课，但我想帮助理解这些算法的理论 . 伪代码也不会受到伤害 .

3 回答

0
在树的上下文中，深度和广度优先搜索可能更容易理解 .
```
A
   / \
  B   C
 /
D
```
在访问兄弟节点之前， depth-first search （DFS）将访问子节点 . 部门首先搜索上述树将按以下顺序访问项目：
```
A B D C
```
C是B的兄弟，因此在搜索B的后代后进行搜索 .

A breadth-first search （BFS）在访问子节点之前搜索兄弟节点 . 对上述树进行广度优先搜索将按以下顺序访问项目：
```
A B C D
```
B和C是兄弟姐妹，所以他们在B的孩子D之前被搜查 .
回复于 2024-05-02T19:48:53+08:00
2
Breadth first search 本质上意味着：访问所有父节点，然后访问所有子节点 .

虽然 depth first search 表示：首先访问所有子节点，直到到达叶节点（没有子节点的节点），然后访问下一个父节点和所有子节点，并继续，直到您访问所有节点 .

这里有图片（取自维基百科），显示了在广度优先搜索中访问节点的顺序（由树表示）：

在这里，您可以获得深度优先搜索的相应图片：

伪代码

广度优先搜索：
```
def BFS(G,v):

    create a queue Q
    enqueue v onto Q
    mark v

    while Q is not empty:
      t = Q.dequeue()

      if t is what we are looking for:
          return t

      for all edges e in G.incidentEdges(t) do:
         o = G.opposite(t, e)

     if o is not marked:
          mark o
          enqueue o onto Q
```
基本上你是在创建一个队列并在其中添加所有节点...记住一个队列是先进先出的数据结构 .

深度优先搜索：
```
def DFS(G, v):
    label v as explored

    for all edges e in G.incidentEdges(v) do:

      if edge e is unexplored then:

          w = G.opposite(v, e)

          if vertex w is unexplored then:

              label e as a discovery edge
              recursively call DFS(G, w)
      else 
         label e as a back edge
```
现在，对于这个，你几乎设置了一个探索的旗帜，如果你已经探索了所有这些，那么你已经按顺序进行了深度优先搜索 .
回复于 2024-05-02T19:48:53+08:00
2

查看我在BFS和DFS上的帖子http://nekocm.blogspot.com/search/label/Data%20Structures

希望能帮助到你！

回复于 2024-05-02T19:48:53+08:00

5x5数字网格中的广度优先和深度优先搜索算法

3 回答

相关问题