algorithm - 如果只有访问者，父代和距离矢量，则可以预购树木漫步

Question

我在邻接矩阵图上实现了prim算法该算法的结果是3个向量：avisited、aparent和adistance向量。在算法结束时，对于所有visited[i] == truei = 0..N-1是parent[i]的父级，i是从distance[i]到parent[i]的距离。
现在，考虑到这三个向量，我想如果我可以做一个深度优先搜索，而不需要创建一种树结构，通过它我可以应用深度优先搜索。
i应该从为构建最小生成树而选择的第一个节点开始。我选择这个节点作为dfs节点。问题是，一旦我到达这个节点，我就不知道哪些节点是它的子节点（仅给出上面的3个向量），除非我遍历所有节点并检查它们的父节点在这种情况下，给定节点的子节点集0，我应该选择C，这样i。
我应该什么时候停下来当有一个带有C_i的节点时（即没有子节点）在这种情况下，我可以回到min(distance[C_i])的父节点，检查它是否还有一个未访问的子节点。
现在还存在一个问题，即每当我们访问一个节点时，都要对其进行标记。我想我可以有另一个向量来跟踪已经递归的节点。
我还需要保留一份他们被访问的顺序列表。这应该只是在递归时将节点添加到列表中的问题。
我将如何表示预订树行走这应该只是我刚才提到的节点列表。（对吧？）
这是对的吗如果是，这是一个好办法吗？你知道还有更好的方法吗？

Answer 1

现在，考虑到这三个向量，我想如果我可以做一个深度优先搜索，而不需要创建一种树结构，通过它我可以应用深度优先搜索。
您只需使用parent数组，就可以轻松地在预期的Θ（| V |）时间内遍历生成树。
创建节点id到链接节点列表的字典children（eacg初始化为空列表）。
扫描parent数组，如果parent[i] = j，则将i添加到children[j]（recall是一个列表）。
在伪代码中：

children = dictionary of nodes to lists
for i in 1, ..., len(parent):
     children[parent[i]].add(i)        

根据定义，如果j是最小生成树中i的父代，则i是j的子代之一。构造 children是长度 parent的预期线性时间。
调用 MST-DFS(0)（下面定义 MST-DFS）现在将按DFS顺序调用节点：

MST-DFS(j):
    print j # Current node in DFS order
    for i in children[j]:
        MST-DFS(i)

运行此部分在 parent的长度上是线性的。