在图中使用 BFS 查找路径
Find a path with BFS in a graph
我想在具有 bfs 的图中找到两个节点之间的路径。我写了一个以正确顺序访问所有节点的函数（不确定它是否有效，但对我来说似乎是正确的）但我需要存储路径（包含构成路径的所有边的列表）并且我不不知道该怎么做：\
有人可以帮助我吗？提前致谢:)
您创建了一个 p 的 parent 数组。因此，如果 p[u] = v 在从源到 u 的路径中存在从 v 到 u 的边。其中源顶点的parent为null.
所以当我们在当前顶点v时，在将它的相邻顶点u插入队列之前，我们使p[w] = v。当您找到目标顶点时，您将在数组 p 中向后移动。从目标顶点w开始，p[w]是w的parent，p[p[w]]是parent的parent w 等等。
这可以是其中一种方法。
在这种方法中，您保留一个列表队列，您可以在其中获取列表并从该列表中获取第一个节点。
找到该节点的 adj() 并为每个未访问的节点在队列中添加一个新的 path+[node] ，如果到达目的地 return 即 path+[node] .
step 1 : create a queue of to hold the paths.
step 2 : add the source as [ source ] in the queue
step 3 : while the queue is not empty get one path from it
(as this works for both bfs and dfs thats why "get" not "dequeue" or "pop")
step 4: get the last node of that path (list)
step 5: get the adj of that node and for each not explored create a new path i.e oldpath +[adj node]
step 6:if the adj node is what u want then return the path else add the path to the queue
希望对您有所帮助。
我想在具有 bfs 的图中找到两个节点之间的路径。我写了一个以正确顺序访问所有节点的函数（不确定它是否有效，但对我来说似乎是正确的）但我需要存储路径（包含构成路径的所有边的列表）并且我不不知道该怎么做：\
有人可以帮助我吗？提前致谢:)
您创建了一个 p 的 parent 数组。因此，如果 p[u] = v 在从源到 u 的路径中存在从 v 到 u 的边。其中源顶点的parent为null.
所以当我们在当前顶点v时，在将它的相邻顶点u插入队列之前，我们使p[w] = v。当您找到目标顶点时，您将在数组 p 中向后移动。从目标顶点w开始，p[w]是w的parent，p[p[w]]是parent的parent w 等等。
这可以是其中一种方法。
在这种方法中，您保留一个列表队列，您可以在其中获取列表并从该列表中获取第一个节点。
找到该节点的 adj() 并为每个未访问的节点在队列中添加一个新的 path+[node] ，如果到达目的地 return 即 path+[node] .
step 1 : create a queue of to hold the paths.
step 2 : add the source as [ source ] in the queue
step 3 : while the queue is not empty get one path from it
(as this works for both bfs and dfs thats why "get" not "dequeue" or "pop")
step 4: get the last node of that path (list)
step 5: get the adj of that node and for each not explored create a new path i.e oldpath +[adj node]
step 6:if the adj node is what u want then return the path else add the path to the queue
希望对您有所帮助。