在下面的代码中，图上深度优先搜索的时间复杂度是如何变成O(V+E(的？
Using a Python dictionary to act as an adjacency list
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}
visited = set() # Set to keep track of visited nodes.
def dfs(visited, graph, node):
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
# Driver Code
dfs(visited, graph, 'A')
if node not in visited:
因此，任何顶点的访问次数都不会超过1次，而且对于任何顶点，这种情况都不会被检查超过次，我们知道次的总和是O(E(，并且
for neighbour in graph[node]:
因此，连接到每个节点的每个边缘都被认为是DFS 的可能步骤
因此，O(V+E((假设在您的集合中插入和删除O(1((的时间复杂性
除了dfs的第一次调用外，dfs的每一次调用都将唯一地对应于一条边。由于visited机制，对于node和neighbor的相同值，不可能进行dfs的递归调用。
实际上，这是这个算法的唯一决定因素，所以它是O(E(。
如果图形断开连接，则此算法不会访问所有节点。当这种情况必须处理时，驱动程序代码应该如下所示：
for node in graph:
dfs(visited, graph, node)
随着这种变化，复杂性变为O(V+E(。这是因为在断开连接的图中，节点可能比边多得多，因此O(E(不会捕获复杂性，并且驱动程序代码中的循环成为决定因素。因此，你可以说它是O(MAX(V，E((，它与O(V+E(相同。