確定是否無向圖連接

Question

我遇到了這個帖子從前陣子：

Best algorithm to determine if an undirected graph is a tree

它說，以確定是否無向圖是一棵樹，你只需要檢查它是否有周期。但是，您是否必須確保圖形已連接？我被教導說，一棵樹連接着和非循環。如何檢查非循環性是否足夠？

謝謝。

Answer 1

你說得對。如果圖是非循環的，那麼它是一個森林。另外，如果它只有一個組件，那麼它就是一棵樹。

提到的算法的作用是查找後沿。如果它找到一個，那麼該圖不是一棵樹。如果它沒有找到一個，並且該算法在用完邊緣之前訪問了n-1條邊，那麼它就是一棵樹，因爲訪問過n-1條邊意味着該圖確實連接了（具有n個頂點的樹具有n- 1個邊緣）。如果算法跑出邊緣但未達到n-1個訪問邊，則表示圖不連通，因此它不是樹。