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

我不想知道答案，但我很难跟踪节点。意思是，假设我有节点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）不检查完整路径。

最佳答案

保持path variable以在遇到顶点时存储顶点当找到end顶点时，path变量将具有路径。
查找伪代码以供参考原谅代码中的任何小错误

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

根据您的代码，当您找到目标顶点时，访问的堆栈包含路径中的元素。
我希望有帮助。

关于python - 使用邻接矩阵在无向加权图中进行深度优先搜索？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39839695/