dfs和bfs差别_BFS和DFS之间的区别

古城微笑少年丶 2022-12-07 13:56 186阅读 0赞

![0f76213b219d1be3b9b0f435f8e8bbfd.png][]

dfs和bfs差别

Here you will learn about difference between BFS and DFS algorithm or BFS vs. DFS.

在这里，您将了解BFS和DFS算法或BFS与DFS之间的区别。

Breadth First Search (BFS) and Depth First Search (DFS) are two popular algorithms to search an element in Graph or to find whether a node can be reachable from root node in Graph or not. And these are popular traversing methods also.

广度优先搜索(BFS)和深度优先搜索(DFS)是在Graph中搜索元素或查找是否可以从Graph中的根节点访问节点的两种流行算法。 这些也是流行的遍历方法。

When we apply these algorithms on a Graph, we can see following types of nodes.

当我们在图上应用这些算法时，我们可以看到以下类型的节点。

1.  **Non-Visited nodes:** These nodes not yet visited.
    
    **非访问节点：**这些节点尚未访问。
2.  **Visited nodes:** These nodes are visited.
    
    **被访问的节点：**这些节点被访问。
3.  **Explored nodes:** A node is said to be explored when it was visited and all nodes which are connected (adjacent) to that node also visited.
    
    **探索的节点：**据说一个节点在被访问时会被探索，并且所有(相邻)连接到该节点的节点也都被访问过。

## BFS和DFS之间的区别 **(**Difference between BFS and DFS**)** ##

<table> 
 <tbody> 
  <tr> 
   <td><strong>S. No.</strong></td> 
   <td><strong>Breadth First Search (BFS)</strong></td> 
   <td><strong>Depth First Search (DFS)</strong></td> 
  </tr> 
  <tr> 
   <td>1.</td> 
   <td>BFS visit nodes <strong>level by level</strong> in Graph.</td> 
   <td>DFS visit nodes of graph&nbsp;<strong>depth&nbsp;wise</strong>. It visits nodes until reach a leaf or a node which doesn’t have non-visited nodes.</td> 
  </tr> 
  <tr> 
   <td>2.</td> 
   <td>A node is fully explored before any other can begin.</td> 
   <td>Exploration of a node is suspended as soon as another unexplored is found.</td> 
  </tr> 
  <tr> 
   <td>3.</td> 
   <td>Uses Queue data structure to store Un-explored nodes.</td> 
   <td>Uses Stack data structure to store Un-explored nodes.</td> 
  </tr> 
  <tr> 
   <td>4.</td> 
   <td>BFS is slower and require more memory.</td> 
   <td>DFS is faster and require less memory.</td> 
  </tr> 
  <tr> 
   <td>5.</td> 
   <td><strong>Some Applications:</strong> 
    <ul> 
     <li>Finding all connected components in a graph.</li> 
     <li>Finding the shortest path between two nodes.</li> 
     <li>Finding all nodes within one connected component.</li> 
     <li>Testing a graph for bipartiteness.</li> 
    </ul> </td> 
   <td><strong>Some Applications:</strong> 
    <ul> 
     <li>Topological Sorting.</li> 
     <li>Finding connected components.</li> 
     <li>Solving puzzles such as maze.</li> 
     <li>Finding strongly connected components.</li> 
     <li>Finding articulation points (cut vertices) of the graph.</li> 
    </ul> </td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> <strong>序号</strong> </td> 
   <td> <strong>广度优先搜索(BFS)</strong> </td> 
   <td> <strong>深度优先搜索(DFS)</strong> </td> 
  </tr> 
  <tr> 
   <td> 1。 </td> 
   <td> BFS在Graph中<strong>逐级</strong>访问节点。 </td> 
   <td> DFS访问图<strong>深度明智的</strong>节点。 它会访问节点，直到到达叶或没有未访问节点的节点为止。 </td> 
  </tr> 
  <tr> 
   <td> 2。 </td> 
   <td> 在开始任何其他节点之前，必须先充分探究一个节点。 </td> 
   <td> 一旦发现另一个未探索节点，就会暂停对该节点的探索。 </td> 
  </tr> 
  <tr> 
   <td> 3。 </td> 
   <td> 使用队列数据结构存储未探索的节点。 </td> 
   <td> 使用堆栈数据结构存储未探索的节点。 </td> 
  </tr> 
  <tr> 
   <td> 4。 </td> 
   <td> BFS较慢，需要更多的内存。 </td> 
   <td> DFS更快并且需要更少的内存。 </td> 
  </tr> 
  <tr> 
   <td> 5， </td> 
   <td> <strong>一些应用：</strong> 
    <ul> 
     <li> 在图中查找所有连接的组件。 </li> 
     <li> 查找两个节点之间的最短路径。 </li> 
     <li> 查找一个连接的组件内的所有节点。 </li> 
     <li> 测试图的二等性。 </li> 
    </ul> </td> 
   <td> <strong>一些应用：</strong> 
    <ul> 
     <li> 拓扑排序。 </li> 
     <li> 查找连接的组件。 </li> 
     <li> 解决迷宫等难题。 </li> 
     <li> 查找牢固连接的组件。 </li> 
     <li> 查找图形的关节点(切顶点)。 </li> 
    </ul> </td> 
  </tr> 
 </tbody> 
</table>

**Example**

**例**

Considering A as starting vertex.

将A作为起始顶点。

![Difference between BFS and DFS][]

[Image Source][]

[图片来源][Image Source]

**Note:** There are many sequences possible for BFS and DFS. Using permutations we can find how many are there.

**注意：** BFS和DFS有许多可能的序列。 使用排列，我们可以找到其中的数目。

Comment below if you found any information incorrect or missing in above tutorial for difference between dfs and bfs.

如果您发现上面的教程中的dfs和bfs之间存在差异，则您在以下教程中发现任何不正确或缺失的信息时，请在下面发表评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2017/06/difference-between-bfs-and-dfs.html][https_www.thecrazyprogrammer.com_2017_06_difference-between-bfs-and-dfs.html]

dfs和bfs差别

[0f76213b219d1be3b9b0f435f8e8bbfd.png]: /images/20221123/b16502adb87c41eabafec9ae60b08d54.png
[Difference between BFS and DFS]: /images/20221123/b65718a52a6d4080a8a12bd0a479f39b.png
[Image Source]: http://freefeast.info/difference-between/difference-between-bfs-and-dfs-bfs-vs-dfs/
[https_www.thecrazyprogrammer.com_2017_06_difference-between-bfs-and-dfs.html]: https://www.thecrazyprogrammer.com/2017/06/difference-between-bfs-and-dfs.html