知道是否連接了無向圖的最有效的算法

Question

我一直在試圖找到一個算法來搜索圖是否連接。該圖是無向的，我只想找到a解決方案（可能有多個）或者沒有。我正在尋找一個ALG。它執行接近線性時間，可能是O（logN）或O（NlogN）。

DFS可以完成任務嗎？或者對於這個特定問題還有其他的選擇嗎？

Answer 1

這取決於你如何定義N，如果N是頂點數，輸入本身的大小可能是O(N^2)，並且你將需要讀取所有它（除非你有一些特定的輸入順序，並且可能會改變）。

DFS運行於O(|V|+|E|)（節點數+邊數），並且可以通過簡單地計算您發現的新頂點的數量並完成後檢查該數是否爲|V|來查找圖是否連接。