爲圖形構建BFS樹的複雜性是什麼？

-1

我知道一個BFS需要O（n + m）時間，其中n是節點，m是弧。爲圖形構建BFS樹的複雜性是什麼？

如何在做BFS的同時構建樹？

只要在最壞的情況下樹完全不平衡，它是否會添加另一個n？

2012-07-09 Zagorax

不能完全確定我下面，但如果由：

它增加了另一N

你指的是複雜性將是O(n+m+n)，注意O(n+m+n) = O(n+m)，所以是不是真的發出這裏。

樹的建築物可以在O(n+m)來完成，因爲它可以表示爲一個數組a[1,...,n]其中a[i] = j if and only if node i is connected to node j in the tree（和用於根特殊標記）

所以，BFS期間，當節點v「發現」節點u，你只需要做a[u]=v，這是在固定的時間完成，並準確地完成n倍，因此總的複雜性仍然O(n+m)

2012-07-09 14:42:27 amit

你說v'發現節點時，''點我u'已添加'a [v] = u'。它不應該是相反的嗎？同一個節點可以發現更多的節點。這是一個錯字還是我錯過了什麼？ – Zagorax 2012-07-09 15:20:55

是的。謝謝你的糾正。 – amit 2012-07-09 15:24:24

還有一個問題。如果我們想把樹建成一棵「樹」而不是一個數組呢？我的意思是，如果我有一個真正的樹形結構，我可以確定節點距離源節點的深度。在最壞的情況下建造這樣的結構有多昂貴？ – Zagorax 2012-07-09 21:19:39

回答