Python字典实现深度优先搜索

Question

我看到的深度优先搜索的伪代码让我非常困惑，因为它与我的具体问题没有关系。我正在尝试确定“有向图”是否强连通。

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

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

我看到我可以将“Austin”作为起点传递。但是，我如何将“Austin”设置为已访问，并且如何查看哪些节点与“Austin”相邻？

此外，我如何使用该算法返回图是否强连通的true或false？

我只是很难从伪代码转换成代码。感谢任何帮助。

- Coder117

---

你的数据结构不适合实现一般图，因为它不允许从一个顶点出发有多条边。字典的值应该是目的地的列表。 - DYZ

Answer 1

我可以看到我可以将'Austin'作为起点。但是我该如何将'Austin'设置为已访问，以及如何查看与'Austin'相邻的节点呢？

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

另外，我该如何使用这个算法返回图是否强连通的真或假？

这只是一个实用的DFS函数，要找出图是强连通还是非强连通，需要运行DFS两次。基本上，提示是你想知道在运行DFS时是否得到了树或森林。

在我看来，您应该更新您的数据结构，使每个键的值都是列表（它具有边缘的顶点）。您还可以在列表中存储权重，以防以后需要使用它们。

- Stuti Rastogi