algorithm - 使用邻接矩阵修改深度优先搜索算法以搜索特定端节点

Question

因此，对于具有 N 个节点的图，我有一个大小为 N x N 的邻接矩阵。我想进行一次 Depth First Search通过此矩阵来查找是否存在从 Source 节点到 Destination 节点的路径。如果它存在，我想打印路径。

在下面的伪代码中，它使用矩阵/图 G 来查找可以用 v 的起始节点访问的所有顶点。我将如何修改此算法，以便我可以得到类似于此的内容:procedure DFS(G,v,d) 其中 d 是我要搜索的目标节点？

procedure DFS(G,v):
    label v as discovered
    for all edges from v to w in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G,w)

另外作为旁注，我将如何添加返回它发现的路径的所有边的总权重的能力？

Answer 1

算法需要在两个方面进行修改

1. 它需要在找到目的地时停下来
2. 它需要产生一条到达目的地的路径

在下面的伪代码中，路径变量 P 开始时是一个空列表。找到目的地后，将目的地节点放入P。然后随着每一级递归的返回，当前节点 w 被附加到路径中。当顶级调用返回时，P 包含完整路径。只有一个问题，路径是相反的:目的地到源头。所以你必须扭转局面。

procedure DFS(G,v,d,P=empty):
    if v equals d
        initialize P with d
        return P
    label v as discovered
    for all edges from v to w in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G,w,d,P)
            if P is not empty
                append v to P
                return P
    return empty