returns 组顶点等距离（不是无限）的顶点的算法

Question

编写一个算法，给定图 G 和 G 的顶点 t，returns 由 t.

等距离（不是无限）的顶点集

图G如下：

考虑到 t = A，算法应该 return:

距离为 0 的顶点集：{A}
距离为 1 的顶点集：{B, D}
距离为 2 的顶点集：{E, F}
距离为 3 的顶点集：{C}
距离为 4 的顶点集：{}
距离为 5 的顶点集：{}

我认为该算法可以通过简单修改宽度算法来实现，该算法总结了所有顶点与源顶点的距离。我该如何编写伪代码？我有点糊涂..

非常感谢

Answer 1

可以使用如下伪代码：(可以通过设置每个节点的距离属性为father.distance + 1来保存BFS中到源节点的距离，初始节点的距离为 0。每个节点的初始距离也是无限的）

 BFS(G,targetNode), remember to save all the distances for each node.

 for i = 0 to G.v.size

     print "nodes with distance i :"

     for each Vertex v in G:

         if v.distance == i

             print v

returns 组顶点等距离（不是无限）的顶点的算法

Algorithm that returns sets of vertices that are equal distance (not infinite) by a Vertex

algorithm

graph

directed-graph

breadth-first-search