python - 深度优先搜索的输出中缺少节点

Question

graph = {}

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited

n = int(input())
drinks = [d for d in input().split()]
m = int(input())
obs = []
for _ in range(m):
    di, dj = input().split()
    obs += [(di, dj)]

for drink in drinks:
    graph[drink] = []

for drink1, drink2 in obs:
    graph[drink1].append(drink2)
    
order = dfs(graph,drinks[0], [])
print(order)

大家好!

我应该输入一定数量的饮料及其名称。之后，我必须输入组合的数量以及实际上充当图形顶点的组合

示例输入为:

7
A B C D E F G
12
A B
A C
A D
B D
B E
C F
D C
D F
E D
G D
G E
G F

问题是我的输出是['A', 'B', 'D', 'C', 'F', 'E']。它缺少 'G' 并且不是三个可能的输出之一 ['A','B','G','E','D','C',' F']、['A'、'G'、'B'、'E'、'D'、'C'、'F'] 或 [ 'G'、'A'、'B'、'E'、'D'、'C'、'F']。我不知道为什么

Answer 1

您构建的图是一个有向图，在这种情况下，没有其他节点指向节点G。这意味着 DFS 无法访问 G，除非 DFS 在 G 本身启动。下面是该图的说明:

如果您打算使用无向图，则可以通过更改将边添加到图中的循环来修复此行为:

for drink1, drink2 in obs:
    graph[drink1].append(drink2)
    graph[drink2].append(drink1)

在本例中，您将构建以下无向图(注意没有箭头):

最后，您可能应该更改 dfs 函数以使用 set 而不是列表来跟踪访问的节点，因为检查元素是否包含在列表需要 O(n) 时间，而集合则需要 O(1) 时间:

def dfs(graph, node):
    visited = set()
    if node not in visited:
        visited.add(node)
        for n in graph[node]:
            dfs(graph, n)
    return list(visited)