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']。我不知道为什么

标签： pythongraph

Answer 1

您构建的图是有向图，在这种情况下，没有其他节点指向 node G。这意味着GDFS 无法访问，除非 DFS本G​​身启动。这是图表的说明：

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

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

在这种情况下，您将构建以下无向图（注意没有箭头）：

最后，您可能应该更改您的dfs函数以使用 aset而不是列表来跟踪访问的节点，因为检查元素是否包含在列表中需要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)