使用鄰接矩陣在無向加權圖中進行深度優先搜索？

我不想得到答案，但我無法跟蹤節點。含義，說我有節點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)

如果邊緣被unweighed這會更容易些，但我基本上只要添加了當前節點的所有鄰居，直到找到目標節點，然後我想返回路徑。但在這種情況下，我知道這是因爲1）我不知道如何檢查它是否是目標節點，因爲我只存儲節點鄰居，並且2）不檢查完整路徑。

來源

2016-10-03 VDog

找到目標時，您可以跟蹤訪問節點和相應的重量，直到那時..不知道它是否有幫助。 –

您正在使用哪種算法？你可以在問題中粘貼你的代碼嗎？ –

你的問題還不夠清楚。你想通過運行DFS來實現什麼？ –

維護一個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。到你的代碼中，當你找到目標頂點時，訪問過的棧將包含路徑中的元素。

我希望它有幫助。

來源

2016-10-03 20:47:53

謝謝，但是如何得到一個參數是列表路徑？但是，這是無用的！ – VDog

這是一個僞代碼。 U應該傳遞一個合適的數據類型來存儲路徑。例如：隊列，堆棧，數組等 –

使用鄰接矩陣在無向加權圖中進行深度優先搜索？

回答

相關問題