我不明白 BFS 和 DFS 對于 BFS 的這些復雜性，它寫的時間復雜度是（d 是樹中解決方案節點的深度，b 是節點兒子的最大數量）
空間復雜度寫為
DFS 的時間復雜度是（m 是樹的最大深度）
其空間復雜度為
有人可以解釋一下這些來自哪里嗎
uj5u.com熱心網友回復：
對于 BFS，每次迭代都在探索一個節點佇列，構建下一個佇列并遞回到其中。
def bfs(startNode, target):
queue = [startNode]
while len(queue) > 0:
next_queue = []
for node in queue:
if node == target: return True
next_queue.append(node.children)
queue = next_queue
return False
起初，佇列只有一個元素，但是因為佇列中的每個節點都將其所有子節點都添加到下一個佇列中，并且每個節點最多可以有 b 個子節點，所以佇列的大小可以增加 b 倍每一次迭代。您可能在第一次迭代的佇列中有 1 個節點，然后在第二次回圈中最多有 b 個節點，這些 b 個節點中的每一個都可以自己將 b 個節點添加到第三個佇列中，產生 b*b = b^2 個節點，然后 b^3節點下一個回圈，依此類推。這可以一直持續到在深度 d 處到達目標節點，此時佇列中最多可能有 b^d 個節點。因為佇列被保存在記憶體中，這需要 O(b^d) 空間，并且因為佇列中的每個節點在回圈的每次迭代中（大概）以恒定時間處理，時間復雜度如您所說的 O(1 b b^2... b^d) = O(b^{d 1})。
關于 dfs：
def dfs(node, target):
if node == target: return True
found = false
for child of node.children:
found = dfs(child, target)
if found: break
return found
對于 dfs，不能保證您的搜索采用正確的分支直接到達目標節點。您盡可能深入，遞回地探索每個節點的第一個子節點，直到搜索觸底為止，然后再分支到一邊。因此，您可以搜索比目標節點的深度 d 更深的搜索，并且在最壞的情況下，可以探索到最大深度并在找到目標之前處理整個圖。由于 Graph 最多可以包含 b^m 個節點，因此 dfs 的時間復雜度為 O(b^m)。要分析空間復雜度，請注意您可以在搜索觸底之前進行 m 次遞回呼叫。進行函式呼叫需要空間：深度為 m 的呼叫堆疊至少需要 O(m) 空間。但是，對給定節點的每個遞回呼叫都參考該節點最多 b 個子節點，需要 O(b) 空間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/369665.html