隣接行列を使用した、無向グラフの重み付けグラフの深さの最初の検索？

Question

私は答えは欲しくないが、私はノードを追跡するのに問題がある。それはかどう

[ 
    [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] 
] 

：意味は、Iが0で開始され、そして7が目標であるノード0、1、2、3.4、5、6、7を持っていると、私はそうのような隣接行列を作っ0の場合、ノード間にリンクはありません。そうでない場合は、1より大きい場合、その数はそれらのノード間のエッジの重みです。

パスに対して、実際のノードが何であるかを特定することができません。

私は目標を見つけることができますが、私はゴールへの道筋をどのように表示するのか分からず、総重量はいくらですか？

EDIT：ここ は（これは動作しませんが、これは一般的な考え方である）私が達成しようとしているものです：

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) 

エッジが、これは容易になるだろうunweighed、しかし、私はされた場合私は目標ノードを見つけるまで、私はスタックにそれを訪問していない限り、基本的に現在のノードのすべての隣人を追加し、私はパスを返すしたい。しかし、この場合、私はそれが壊れていることを知っています。なぜなら、目標ノードであるかどうかを確認する方法がわからないからです。ノードの隣接ノードのみを格納するためです.2）完全なパスをチェックしません。

Answer 1

頂点を保存するためにpath variableを維持します。 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 

Acc。あなたのコードに、目標頂点が見つかったとき、訪問先のスタックにはパスの要素が含まれています。

私はそれが助けてくれることを願っています。