algorithm - 广度优先搜索与深度优先搜索

有人能简单解释一下bfs和dfs吗？
我想知道什么时候更喜欢朋友而不是外勤人员。

最佳答案

bfs和dfs都是图遍历算法，它们之间的区别在于每个算法遍历图的方式。
dfs，假设您有下面的图，我们希望开始从node1遍历：

          1
         / \
        2   3
       / \   \
      4   5   6

Dfs表示深度优先搜索，因此它将以这种方式遍历图形：
从node1开始，然后查找其子节点。它找到node2。
转到node2然后查找其子节点它找到node4。
转到node4则发现它没有子节点。
再次转到nodeUp并查看其其他子节点它找到node2。
转到node5然后发现它没有子节点。
再次转到node5并发现它没有更多的子节点。
转到node2然后查找其子节点。它找到node1。
转到node3然后查找其子节点它找到node3。
转到node6并发现它没有子节点。
转到node6并发现它没有更多的子节点。
上到node3并发现它没有更多的子节点，因此此时已完成图形遍历。
如果你注意到这个算法首先是如何深入的，那么一旦它发现node1是node2的子节点，它就开始寻找它的子节点，而不关心node1（node1）的其他子节点，然后在到达最深的可能节点（nodes3，4）之后，它开始寻找node5的其他子节点。
另一方面，考虑到我们希望使用bfs算法遍历同一个图。当使用bfs时，您开始将图形节点视为级别，每个级别都比它之后相对于开始遍历的节点更接近。也就是说：

          1         (level 0)
         / \
        2   3       (level 1)
       / \   \
      4   5   6     (level 2)

因此，遍历图形将是：
从nodeUp开始，然后查找其子节点（nodes1，1）[下一级]。
遍历级别1（2，3）的节点并查找其子节点（节点2，3，4）[下一级别]。
遍历级别2（5，6，4）的节点并查找此子节点（无子节点）[无下一级别]。
然后图形遍历在这一点结束。
您可以在这里认识到，节点的直接子节点（下一级）始终是最接近它的节点，因此使用bfs而不是dfs的优点是，它可以保证您使用尽可能短的路径从节点5到达节点6。
但是要注意，BFS算法不能为所有类型的图找到最短路径我在这个例子中提到的图是未加权图（所有边/路径都相同的图）。如果图是加权的（边/路径具有权重，但不相同），则必须使用另一种考虑到这一点的算法（如Dijkstra）。

关于algorithm - 广度优先搜索与深度优先搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53856717/