在下面的代碼中，深度優先搜索的時間復雜度如何變成 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')
uj5u.com熱心網友回復：
if node not in visited:
因此，沒有一個頂點被訪問超過 1 次，而且這個條件不會被檢查超過任何頂點的入度次數，我們知道入度的總和是 O(E)，并且
for neighbour in graph[node]:
因此，連接到每個節點的每條邊都被認為是DFS 的一個可能步驟
所以 O(V E) 的時間復雜度（假設你的集合中有 O(1) 插入和洗掉）
uj5u.com熱心網友回復：
除了第一次呼叫 之外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) 相同。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/391647.html