广度优先search在寻找最短path时如何工作？

我已经做了一些研究，我似乎失去了这个algorithm的一小部分。 我明白广度优先search是如何工作的，但是我不明白它究竟是如何使我走到一个特定的path，而不是告诉我每个单独的节点可以在哪里走。 我想解释我的困惑最简单的方法是提供一个例子：

举个例子，假设我有这样一个图表：

我的目标是从A到E（所有的边缘都没有加权）。

我从A开始，因为那是我的起源。 我排队A，然后立即出队A并探索它。 这产生B和D，因为A连接到B和D.因此，我排列B和D.

我将B出队并探索，发现它导致了A（已经探索过）和C，所以我排队C.然后我出队D，并且发现它导致了E，我的目标。 然后我把C出列，并且发现它也导致了E，我的目标。

从逻辑上讲，我知道最快的path是A-> D-> E，但是我不确定广度优先search是如何帮助的 – 我应该如何loggingpath，以便在完成时可以分析结果并查看那么最短path是A-> D-> E？

另外请注意，我实际上并没有使用树，所以没有“父”节点，只有孩子。

Answer 1

从技术上讲，广度优先search（BFS）本身并不能让你find最短path，因为BFS不是寻找最短path：BFS描述search图的策略，但并不是说你必须search任何特别的东西。

Dijkstra的algorithm适应BFS，让你find单源最短path。

为了检索从原点到节点的最短path，需要为图中的每个节点维护两个项目：当前最短距离，以及最短path上的前一个节点。 最初所有的距离都设置为无穷大，所有的前辈都设置为空。 在你的例子中，你将A的距离设置为零，然后继续BFS。 在每个步骤中，检查是否可以改进后代的距离，即从原点到前导的距离加上您正在探索的边的长度小于所讨论的节点的当前最佳距离。 如果您可以改善距离，请设置新的最短path，并记住获取该path的前身。 当BFS队列为空时，select一个节点（在你的例子中是E），并将其前辈遍历回原点。 这会给你最短的path。

如果这听起来有点混乱，维基百科有一个很好的伪代码部分的主题。

Answer 2

如上所述， 只有在以下情况下，BFS才能用于查找图中的最短path：

1. 没有循环

2. 所有边缘具有相同的重量或没有重量。

要find最短path，您只需从源代码开始，执行宽度优先search，并在find目标节点时停止。 你需要做的唯一的附加事情是有一个数组previous [n]将存储每个节点访问的前一个节点。 源的前面可以为空。

为了打印path，从源头到前一个[]数组的简单循环，直到到达目的地并打印节点。 在相似的条件下，DFS也可用于查找图中的最短path。

但是，如果图更复杂，包含加权边和循环，则需要更复杂的BFS版本，即Dijkstraalgorithm。

Answer 3

从这里教程

“它具有非常有用的性质，即如果图中的所有边都是未加权的（或相同的权重），那么第一次访问节点时是从源节点到该节点的最短path”

Answer 4

我浪费了3天
最终解决了一个graphics问题
用于
find最短距离
使用BFS

想分享经验。

 When the (undirected for me) graph has fixed distance (1, 6, etc.) for edges #1 We can use BFS to find shortest path simply by traversing it then, if required, multiply with fixed distance (1, 6, etc.) #2 As noted above with BFS the very 1st time an adjacent node is reached, it is shortest path #3 It does not matter what queue you use deque/queue(c++) or your own queue implementation (in c language) A circular queue is unnecessary #4 Number of elements required for queue is N+1 at most, which I used (dint check if N works) here, N is V, number of vertices. #5 Wikipedia BFS will work, and is sufficient. https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode 

我已经失去了3天，尝试所有以上的select，validation和再次validation上面
他们不是问题。
（尝试花时间寻找其他问题，如果你发现任何问题与5以上）。

---

更多的解释从下面的评论：

  A / \ BC /\ /\ DEFG 

以上假设是你的图
图表向下
对于A，邻居是B＆C
对于B，邻居是D＆E
对于C，邻居是F＆G

比方说，开始节点是A.

1. 当你到达A，B和C时，从A到B＆C的最短距离是1

2. 当到达D或E时，通过B，与A＆D的最短距离是2（A-> B-> D）

同样地，A→E是2（A→B→E）

另外，A-> F＆A-> G是2

所以，现在，而不是1节点之间的距离，如果是6，那么只需乘以6的答案
例，
如果每个之间的距离是1，则A-> E是2（A-> B-> E = 1 + 1）
如果每个之间的距离是6，那么A-> E是12（A-> B-> E = 6 + 6）

是的，bfs可以采取任何path
但我们正在计算所有path

如果你不得不从A到Z，那么我们将所有的path从A移到中间的I，因为会有很多path，我们放弃所有的path，直到I到最短的path，然后继续最短的path到达下一个节点J
如果从I到J有多条path，我们只用最短path
例，
承担，
A – >我们有距离5
（STEP）假设I→J我们有多条path，距离7和8，因为7是最短的
我们取A→J为5（A-> I最短）+8（现在最短）= 13
所以A-> J现在是13
我们现在重复上面的（STEP）J – > K等等，直到我们到达Z

阅读这个部分，2或3次，并在纸上画，你一定会得到我所说的，祝你好运

---

Answer 5

以下解决scheme适用于所有testing用例。

 import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCases = sc.nextInt(); for (int i = 0; i < testCases; i++) { int totalNodes = sc.nextInt(); int totalEdges = sc.nextInt(); Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>(); for (int j = 0; j < totalEdges; j++) { int src = sc.nextInt(); int dest = sc.nextInt(); if (adjacencyList.get(src) == null) { List<Integer> neighbours = new ArrayList<Integer>(); neighbours.add(dest); adjacencyList.put(src, neighbours); } else { List<Integer> neighbours = adjacencyList.get(src); neighbours.add(dest); adjacencyList.put(src, neighbours); } if (adjacencyList.get(dest) == null) { List<Integer> neighbours = new ArrayList<Integer>(); neighbours.add(src); adjacencyList.put(dest, neighbours); } else { List<Integer> neighbours = adjacencyList.get(dest); neighbours.add(src); adjacencyList.put(dest, neighbours); } } int start = sc.nextInt(); Queue<Integer> queue = new LinkedList<>(); queue.add(start); int[] costs = new int[totalNodes + 1]; Arrays.fill(costs, 0); costs[start] = 0; Map<String, Integer> visited = new HashMap<String, Integer>(); while (!queue.isEmpty()) { int node = queue.remove(); if(visited.get(node +"") != null) { continue; } visited.put(node + "", 1); int nodeCost = costs[node]; List<Integer> children = adjacencyList.get(node); if (children != null) { for (Integer child : children) { int total = nodeCost + 6; String key = child + ""; if (visited.get(key) == null) { queue.add(child); if (costs[child] == 0) { costs[child] = total; } else if (costs[child] > total) { costs[child] = total; } } } } } for (int k = 1; k <= totalNodes; k++) { if (k == start) { continue; } System.out.print(costs[k] == 0 ? -1 : costs[k]); System.out.print(" "); } System.out.println(); } } }