Python從圖中獲取所有路徑 [英] Python get all paths from graph

查看:0
本文介紹了Python從圖中獲取所有路徑的處理方法,對大家解決問題具有一定的參考價值,需要的朋友們下面隨著小編來一起學習吧!

問題描述

我正在嘗試查找用戶可以通過網站選擇的路徑。我已使用以下格式表示我的圖表:

graph = { 0 : [1, 2],
          1 : [3, 6, 0],
          2 : [4, 5, 0],
          3 : [1],
          4 : [6, 2],
          5 : [6, 2],
          6 : [1, 4, 5]}

我已經實現了深度優先算法,但它需要進行更改才能發揮作用。它需要返回路徑,而不僅僅是返回節點的順序。

visitedList = [[]]
def depthFirst(graph, currentVertex, visited):
    visited.append(currentVertex)
    for vertex in graph[currentVertex]:
        if vertex not in visited:
            depthFirst(graph, vertex, visited)
    return visited

traversal = depthFirst(graph, 0, visitedList)
print('Nodes visited in this order:')
print(visitedList)

該函數返回以下內容:

[[], 0, 1, 3, 6, 4, 2, 5]

而我想要這樣的東西:

[[0, 1, 3], [0, 1, 6], [0, 2, 4, 6], [0, 2, 5, 6]] 

推薦答案

在傳遞Python中的列表時,它不會深入復制。在這里,使用list.Copy()真的很有幫助。我不確定這是您想要的,但代碼如下:

visitedList = [[]]

def depthFirst(graph, currentVertex, visited):
    visited.append(currentVertex)
    for vertex in graph[currentVertex]:
        if vertex not in visited:
            depthFirst(graph, vertex, visited.copy())
    visitedList.append(visited)

depthFirst(graph, 0, [])

print(visitedList)

它返回所有路徑。

[[], [0, 1, 3], [0, 1, 6, 4, 2, 5], [0, 1, 6, 4, 2], [0, 1, 6, 4], [0, 1, 6, 5, 2, 4], [0, 1, 6, 5, 2], [0, 1, 6, 5], [0, 1, 6], [0, 1], [0, 2, 4, 6, 1, 3], [0, 2, 4, 6, 1], [0, 2, 4, 6, 5], [0, 2, 4, 6], [0, 2, 4], [0, 2, 5, 6, 1, 3], [0, 2, 5, 6, 1], [0, 2, 5, 6, 4], [0, 2, 5, 6], [0, 2, 5], [0, 2], [0]]

我在python3中可以使用列表復制。

這篇關于Python從圖中獲取所有路徑的文章就介紹到這了,希望我們推薦的答案對大家有所幫助,也希望大家多多支持IT屋!

查看全文
登錄 關閉
掃碼關注1秒登錄
發送“驗證碼”獲取 | 15天全站免登陸
亚洲AV无码国产精品