python - 使用邻接矩阵在无向加权图中进行深度优先搜索？

Question

我不想要答案，但我无法跟踪节点。意思是，假设我有节点 0、1、2、3、4、5、6、7，其中 0 是开始，7 是目标，我制作了一个这样的邻接矩阵:

[
    [0, 3, 0, 0, 4, 0, 0, 0],
    [3, 0, 0, 0, 5, 0, 8, 0],
    [0, 0, 0, 4, 0, 5, 0, 0],
    [0, 0, 4, 0, 0, 0, 0, 14],
    [4, 5, 0, 0, 0, 2, 0, 0],
    [0, 0, 5, 0, 2, 0, 4, 0],
    [0, 8, 0, 5, 0, 4, 0, 0],
    [0, 0, 0, 14, 0, 0, 0, 0]
]

如果为 0，则节点之间没有链接，否则，如果大于 1，则该数字是这些节点之间边的权重。

我无法确定实际节点是什么，而不是路径。

我可以找到目标，但我不知道如何显示通往目标的路径，以及总权重是多少？

编辑:这是我要实现的目标(这行不通，但这是总体思路):

def dfs(graph, start, goal):
    stack = []
    visited = []

    stack.append(graph[start])
    visited.append(start)

    while (len(stack) != 0):
        current_node = stack.pop()
        if current_node not in visited:
            visited.append(current_node)

        if current_node = goal:
            return path
        else:
            for nodes in current_node:
                if nodes not in visited:
                    stack.append(nodes)

如果边没有被加权，这会更容易，但我基本上是将当前节点的所有邻居添加到堆栈中，只要我没有访问过它，直到找到目标节点，然后我想返回路径。但在这种情况下，我知道它已损坏，因为 1) 我不确定如何检查它是否是目标节点，因为我只存储节点邻居，以及 2) 不检查完整路径。

Answer 1

维护一个路径变量来存储你遇到的顶点。当您找到 end 顶点时，路径变量将具有路径。

找到伪代码以供引用。请原谅代码中的任何小错误

DFS (vertex start, vertex end, Graph G, list path):
         if(start==end):
              return TRUE
         for vertex in adjacent(start):
            if vertex not in path:     # has not been traversed
               path = path + [vertex]
               a = DFS(vertex, end, G, path)
               if a==TRUE:  # end vertex was found 
                  return TRUE
               path.delete(vertex)  # delete the vertex added,as its not in the path from start to end

累积。对于您的代码，当您找到目标顶点时，访问的堆栈包含路径中的元素。

希望对您有所帮助。