使用Dict的Python深度优先搜索

Question

我一直看到深度优先搜索的伪代码，它与我的具体问题之间的关系完全让我感到困惑。我试图确定一个“有向图”是否是强连通的。

如果我有一个包含2个字符串的dict（第一个表示源，第二个表示目的地）和一个表示边缘权重的可选数字：

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

如何实现DFS的某些元素？我知道我可以从一个顶点“奥斯汀”开始，而“休斯顿”是另一个顶点。但我不明白这些在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)

我只是很难看到这种从伪代码到代码的转换。感谢任何帮助。

Answer 1

我可以看到我可以通过‘奥斯汀’作为我的开始。但是在世界上，我如何设置'Austin'访问，我如何看到哪些节点与'Austin'相邻？

您可以在代码中看到，您弹出了'Austin'，所以我们不会回头看它。在您的数据结构中，您只允许一个顶点的一条边，因此您永远不会有一个以上的邻居。

另外，如果图是强连通的，我怎么用这个算法来返回真或假呢？