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

Question

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

在下面的伪代码中，它使用matrix/graph 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)

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

Answer 1

算法需要修改两处

找到目的地需要停下来
它需要产生一条到达目的地的路径

在下面的伪代码中，路径变量 P 开始时是一个空列表。找到目的地后，将目的地节点放入P。然后作为每个递归级别 returns，当前节点 w 被附加到路径。当顶级调用 returns 时，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

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

Modifying a Depth First Search Algorithm using an Adjacency Matrix to search for specific end-node

algorithm

pseudocode

adjacency-matrix