我想在强连接组件中找到从节点到其他节点的最短路径，节点可以任意选择。两种搜索方法浮现在脑海中的深度优先搜索或广度优先搜索。
可以证明在某些情况下一种比另一种更可取吗？
一种情况可能是稀疏图与密集图 SCC。
问问题
629 次
2 回答
0
BFS 首先访问连接到当前节点的所有节点，因此找到的每个新节点都使用尽可能少的边数连接。另一方面，DFS 跟随每个节点的一条边，直到没有边可以跟随，而不是为您提供所需的最短路径。
于 2018-11-30T23:01:23.547 回答
0
DFS 不保证如果从源顶点开始访问另一个节点 2 之前访问节点 1，则节点 1 比节点 2 更靠近源。
从 DFS 的递归性质可以很容易地看出这一点。它访问“更深”的节点，或者您可以先说离源节点更远。它从源顶点尽可能远，然后返回到已访问顶点的未访问相邻节点。
另一方面，BFS 总是按照与源的距离递增的顺序访问节点。它首先访问图的同一“级别”的所有节点，然后进入下一个级别。
此外，使用非递归算法 (BFS) 纯粹在实际方面更具生产力。
于 2018-11-07T21:09:11.293 回答