return 树图中从一个顶点到所有其他顶点的路径的算法

Question

如果我有一棵树是图 G 上的最小生成树，并且我想计算从一个顶点到树上所有其他顶点的路径，这样做的最佳方法是什么？

我认为最好使用堆栈数据结构来存储路径，并递归地使用 DFS - 将每个新顶点添加到堆栈中，一旦没有更多未访问的节点，将该堆栈存储为路径，并继续.. 或者，在伪代码中：

P = {}
stack = []
visited = []
dfs(root_node, stack, visited, P)

def dfs(curr_node, stack visited, P):
    push curr_node to stack
    for all n connected to curr_node
        if n not in visited
            dfs(n, stack visited, P)
    add current stack to P
    pop curr_node from stack
    mark curr_node as visited

这行得通吗？人们可以建议我这样做的更好方法吗？

另外，如果我想在 matlab 中实现它，有什么我应该考虑的因素吗？我知道 matlab 中没有堆栈数据结构，但我想我可以使用这样的向量：

% push
stack = [stack, val];
% or
stack(end+1) = val;

% pop
stack(end) = [];

可以用吗？哪个版本的推送会更好？

Answer 1

如果您在进入相邻的图形节点之前将您的节点标记为已访问，则您的算法将起作用。否则，您的 DFS 将永远在根节点和邻接列表中的第一个节点之间反弹。当然，如果你的图表是有向的，那不会发生。

push 和 pop 通过增长和缩小向量在 MATLAB 中适用于小型堆栈。但是如果你有很多节点，你最好用经典的方式实现它。即预先分配数组，声明一个堆栈指针，并对其进行操作：

N = size(adjacency_matrix, 1); the number of nodes % create stack = zeros(N,1); sptr = 0; % push sptr = sptr + 1; stack(sptr) = val; % pop if sptr > 0 sptr = sptr - 1; end;

否则你最终会得到碎片化的内存和推送新元素的二次执行时间（应该是 O(1)）。

return 树图中从一个顶点到所有其他顶点的路径的算法

algorithm to return the paths from one vertex to all others in a tree graph

tree

matlab

traversal

depth-first-search