無向圖

習題預習

1. 給定一個無向圖，問是否存在任意一條從一個點到另一個點的路徑。

2. 給定一個無向圖，找到其中所有奇環（環的長度為奇數）。

3. 給定一個無向圖，找到其中所有的二分圖（可以把圖的所有點分成兩個集合，使得集合中的所有點之間都不存在邊）。

4. 給定一個無向圖，找到其中所有的橋（刪除此邊後，圖會變成兩個不連通的子圖）。

5. 給定一個無向圖，找到其中所有的連通份量（圖中的所有點都可以通過邊相互到達）。

說明知識

Undirected Graph是一種圖形，其節點（也被稱為頂點）之間的連接是雙向的，沒有方向。在此圖形中，每個節點都可以直接連接到其他節點，且沒有順序。Undirected Graph在許多應用中都很常見，例如社交網路、網路結構、物體之間的連結等等。

以下是一個Undirected Graph的例子，其中節點A、B、C、D和E代表不同的物體，而邊（線）代表物體之間的連接：

A ----- B
|       |
|       |
C ----- D ----- E

在這個例子中，節點A直接連接到節點B和節點C，節點B直接連接到節點A和節點D，節點C直接連接到節點A和節點D，節點D直接連接到節點B、節點C和節點E，節點E直接連接到節點D。注意到這個圖形中的邊沒有方向，所以A和B之間的連接也等同於B和A之間的連接。

這個Undirected Graph可以用來模擬不同物體之間的連接，例如A和B表示兩個人之間的關係，D和E表示兩個物品之間的相似性。當使用這個圖形來分析關係或其他因素時，需要注意其是否是有向的，以確保分析結果的準確度。

彙總重點

1. 無向圖由一組節點和一組邊組成，每個節點可以與其他節點直接相連。

2. 給定一個無向圖，可以用矩陣或鄰接表等方式表示。

3. 無向圖可以應用於許多問題，如社交網絡、互聯網連通性等。

4. 無向圖中的「度」是指每個節點與其他節點相連的邊的數量。

5. 求解無向圖問題的常見算法包括DFS（深度優先搜索）、BFS（廣度優先搜索）、最小生成樹等。

6. 在無向圖中，若從一個節點開始，能夠走遍圖上的所有節點，則該無向圖稱為聯通圖。

7. 無向圖的一個子圖稱為生成子圖，若該子圖包含原圖中的所有節點但並不一定包含所有的邊。

8. 無向圖中的最短路徑是指從一個節點到另一個節點的最短路徑，最短路徑可以利用Dijkstra算法或貝爾福德-福爾德算法求解。

知識測驗

1. 給定一個無向圖和一個起點，找到該圖中所有從起點出發的最短路徑。

答案：BFS（廣度優先搜索）可以在 $O(V+E)$ 的時間內解決此問題。

2. 給定一個無向圖和起點、終點，找到一條從起點到終點的最短路徑。

答案：Dijkstra’s算法可以在 $O(E\log V)$ 的時間內解決此問題。

3. 給定一個無向圖和一個源點，找到該圖中所有點到源點的最大距離。

答案：可以使用DFS（深度優先搜索）計算所有點到源點的距離，然後簡單地選擇最大值。

4. 給定一個無向圖和一個源點，找到該圖中所有點到源點的最小生成樹。

答案：Prim’s算法和Kruskal’s算法都可以解決此問題，其時間複雜度均為 $O(E\log V)$。

5. 給定一個無向圖和一個源點，找到該圖中所有點到源點的最短路徑的平均長度。

答案：可以使用所有源點到其他點的最短路徑之和除以總節點數的方式計算。這可以通過使用Dijkstra’s算法的變形，對每個節點執行BFS來實現。