BFS遍历和完全无向图中的DFS一样吗？
Is BFS traversal the same as DFS in a Complete Undirected Graph?
我有一个作业要求我计算给定完整无向图的最短路径。题目给出一个完整的无向图，基本算法（BFS和DFS）可以提供最短路径。考虑到它是一个完整的无向图，我想知道使用 BFS 或 DFS 是否会产生相同的输出。
我假设图表是用非负权重加权的
- 最短路径在未加权完全图中是微不足道的
- 在无向图中，负权重边将创建负权重循环。这样的图中没有最短路径，因为你总是可以通过添加负循环来改进它。
我还假设您正在寻找两个给定顶点之间的最短路径，因为这是唯一真正适用于 DFS 和 BFS 的最短路径任务。
- 要查找所有单源最短路径，您将使用 Dijkstra
- 要找到所有对的最短路径，您可以使用 Floyd-Warshall
如果图是有限的，DFS 和 BFS 都会给你最短的路径。如果有多个最短路径，DFS 和 BFS 都可以完成，因此它们 return 所有。否则，它们不能保证为您提供相同的最短路径 - 甚至不能保证同一算法的不同实现，它可能会根据边的顺序而有所不同。
DFS 和 BFS 都将具有可怕的时间复杂度 O(n!)，因为它们将遍历整个问题 space，找到从源到目标的所有可能路径。此外，BFS 将具有更大的 space 复杂度（又是 O(n!)）。
对于 DFS 和 BFS，这种复杂性在一般情况下可以通过保持“当前最佳”并修剪无法击败它的分支（因为它们的长度已经更糟）而有所改善。但是您仍然无法接近更合适的算法的速度，例如 Dijkstra 或 A*
我有一个作业要求我计算给定完整无向图的最短路径。题目给出一个完整的无向图，基本算法（BFS和DFS）可以提供最短路径。考虑到它是一个完整的无向图，我想知道使用 BFS 或 DFS 是否会产生相同的输出。
我假设图表是用非负权重加权的
- 最短路径在未加权完全图中是微不足道的
- 在无向图中，负权重边将创建负权重循环。这样的图中没有最短路径，因为你总是可以通过添加负循环来改进它。
我还假设您正在寻找两个给定顶点之间的最短路径，因为这是唯一真正适用于 DFS 和 BFS 的最短路径任务。
- 要查找所有单源最短路径，您将使用 Dijkstra
- 要找到所有对的最短路径，您可以使用 Floyd-Warshall
如果图是有限的，DFS 和 BFS 都会给你最短的路径。如果有多个最短路径，DFS 和 BFS 都可以完成，因此它们 return 所有。否则，它们不能保证为您提供相同的最短路径 - 甚至不能保证同一算法的不同实现，它可能会根据边的顺序而有所不同。
DFS 和 BFS 都将具有可怕的时间复杂度 O(n!)，因为它们将遍历整个问题 space，找到从源到目标的所有可能路径。此外，BFS 将具有更大的 space 复杂度（又是 O(n!)）。
对于 DFS 和 BFS，这种复杂性在一般情况下可以通过保持“当前最佳”并修剪无法击败它的分支（因为它们的长度已经更糟）而有所改善。但是您仍然无法接近更合适的算法的速度，例如 Dijkstra 或 A*