BFS 两个顶点之间的最短路径

Question

大家好，我在 BFS 方面遇到了一些问题，尤其是 2 个顶点 exercise.For 示例：我不想访问所有顶点，但是当我找到我的目标时，我想停止。这个伪代码是正确的吗？（对于代码，我的灵感来自于我的算法书（Goodrich，Tamassia）

BFS(Graph G,Vertex s,Vertex t)
{ Queue q;
  for( all v in G) mark_unvisited(v)
    mark_visited(s)
     q.enqueue(s)
   while(!Q.isEmpty())
    { u=q.front();
        if(u==target)     // is this correct ?
           { break}
         for(all w Adj[u])
           {     if(w==is unvisited)
                   { mark_visited(w)
                      q.enqueue(w)
                    }
            }
        q.dequeue()
   }

提前致谢

Answer 1

是的，没错。一旦您将节点从队列中取出，您就知道您已经找到了到它的最短路径。

希望对您有所帮助！

BFS 两个顶点之间的最短路径

Shortest Path between two vertices with BFS

graph

breadth-first-search