深度优先搜索空集误差

Question

我正在编写一个程序来确定有向图是否强连通。该图由 2 个字符串组成，1 个指向另一个，以及一个可选的数字边权重（如果没有数字则默认为 True）。

我有一个默认字典(dict):

import collections
myDefaultDict = 
        {'A': {'B': True},
         'B': {'C': True},
         'C': {'D': True, 'E': True},
         'D': {'A': True},
         'E': {'C': True}})

然后我有一组字符串：

myNewSet = {'D', 'E', 'C', 'A', 'B'}

然后调用我的深度优先搜索函数：

for i in myNewSet:
    newSet = graph_DFT(i)
    print(newSet)
    break
def graph_DFT(start):
    functionSet = set() # Contains all visited nodes
    myStack = []
    myStack.append(start)
    if not myStack:
        node = myStack.pop()
        for neighbor in myDefaultDict[node]:
            if neighbor not in functionSet:
                functionSet.add(neighbor)
                myStack.append(neighbor)

    return functionSet # Return the set with the visited nodes

问题是print(newSet)。这个示例图是强连通的。那就是你可以从一个顶点到达每个顶点。但是 print(newSet) 显示：

set() # But it should be equal to myNewSet, because this is a strongly connected graph

为什么我的 newSet 是空的？不应该等于myNewSet吗？我需要它，因为这取决于我如何处理我的程序的其余部分，所以我可能在我的 graph_DFT 函数中做错了什么。感谢您的帮助！

Answer 1

正如@MosesKoledoye 所指出的：我只是改变：

if not myStack:

至

while myStack:

深度优先搜索空集误差

Depth First Search Empty Set Error

python

collections

dictionary

graph-theory

set