Python深度第一次搜索字典

我一直看到深度優先搜索的僞代碼，這與我完全混淆了它與我的具體問題的關係。我試圖確定一個'有向圖'是否強連接。Python深度第一次搜索字典

如果我有2串（第一表示源，第二個代表該目的地）和一個可選數目的字典表示邊緣權重：

{'Austin': {'Houston': 300}, 'SanFrancisco': {'Albany': 1000}, 'NewYorkCity': { 'SanDiego': True }}

如何可以實現一些的元件的DFS？我知道我可以從一個頂點'Austin'開始，而'Houston'是另一個頂點。但我看不出任何這在Python代碼

作品就像我有這樣的僞代碼：

function graph_DFS(start): 
    # Input: start vertex 
    S = new Stack() 
    # Mark start as visited 
    S.push(start) 
    while S is not empty: 
     node = S.pop() 
     # Do something? (e.g. print) 
     for neighbor in node’s adjacent nodes: 
      if neighbor not visited: 
       # Mark neighbor as visited 
       S.push(neighbor)

我可以看到，我可以通過「奧斯汀」作爲我的開始。但是我如何在世界上設置「奧斯汀」來訪問，以及如何查看與「奧斯汀」相鄰的節點？

另外我怎麼才能使用這種算法來返回真或假如果圖強連接？

我只是很難看到從僞代碼轉移到代碼。感謝任何幫助。

來源

2017-05-09 Coder117

您的數據結構不適合實現一個通用圖，因爲它不允許從一個頂點有多個邊。字典值應該是_lists_的目的地。 – DyZ

我可以看到，我可以通過'奧斯汀'作爲我的開始。但如何在世界設置「奧斯汀」訪問，以及如何看到什麼節點相鄰 '奧斯汀'？

你可以在代碼中看到你彈出'奧斯汀'，所以我們不會回頭看它。在你的數據結構中，你只允許一個頂點的一條邊，所以你永遠不會有一個以上的鄰居。

加我怎麼才能使用這種算法返回真或假如果圖強連接？

這只是一個實用DFS函數，該算法用於查找圖形是否強連接，需要兩次運行DFS。基本上，提示是你想知道你在運行DFS時是否得到了一棵樹或一片森林。

在我看來，你應該更新你的數據結構，使得每個鍵的值都是一個列表（它有一個邊的頂點）。您也可以將權重存儲在列表中，以備日後需要時使用。

來源

2017-05-09 05:58:06

Python深度第一次搜索字典

回答

相關問題