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深度第一次搜索字典

回答

相关问题