Python深度优先搜索与字典

Question

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

如果我有一个包含 2 个字符串的字典(第一个代表源，第二个代表目的地)和一个代表边权重的可选数字:

{'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)

我可以看到我可以通过“Austin”作为我的起点。但是我究竟如何将“Austin”设置为已访问，以及如何查看哪些节点与“Austin”相邻？

另外，如果图是强连通的，我怎么能使用这个算法返回 true 或 false？

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

Answer 1

I can see that I could pass 'Austin' as my start. But how in the world do I set 'Austin' to visited, and how do I see what nodes are adjacent to 'Austin'?

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

Plus how can I even use this algorithm to return true or false if the graph is strongly connected?

这只是一个实用的DFS函数，判断一个图是否强连通的算法，需要运行两次DFS。基本上，提示是您想知道在运行 DFS 时得到的是一棵树还是一片森林。

在我看来，您应该更新您的数据结构，使每个键的值都是一个列表(它有边的顶点)。您也可以将权重存储在列表中，以备日后需要。