有向圖

習題預習

1. 給定一個有向圖，求其中所有節點的入度和出度。

2. 給定一個有向圖，求其中的強連通分量。

3. 給定一個有向圖，求最短路徑（即從一個節點到另一個節點的最短路徑長度）。

4. 給定一個有向圖，求其中的死亡結點（即出度為0且沒有出邊的節點）。

5. 給定一個有向圖，求其中的贏家（即有一條路徑可以到達所有其他節點的節點）。

說明知識

Directed Graph是一種圖形結構，也稱為網路結構，其中圖的邊線是有指向性的，也就是說，在兩個節點之間存在指向性，可能是從一個節點指向另一個節點，或者沒有連接。Directed Graph也稱為Digraph。

以下是一個以就業網站為例的Directed Graph：

圖片來源：https://commons.wikimedia.org/wiki/File:Directed_graph.png

在此圖中，每個節點代表一個工作職位，而邊緣代表申請者的求職過程。例如，A節點表示一個實習生機會，這是申請人在求職過程中可能會首先申請的職位。接下來，如果申請人被接受，他就可以向B、C、D和E應聘，並且如果沒有被接受，他可能需要尋找其他機會。

Directed Graph的用途包括網路流量、路線優化、關係分析、社交網絡和計算機科學等領域，在這些領域，Directed Graph是一個強大的可視化工具，它可以幫助使用者更好地理解特定問題的複雜性和邏輯關係。

彙總重點

1. 方向性：Directed Graph是有向图，每个节点有一个或多个指向其他节点的边。

2. 节点和边：Directed Graph由一组节点和一组有向边组成，边可以是有向的或无向的。

3. 路径：在Directed Graph中，可以定义路径，即从源节点到目的节点通过一系列边的序列。

4. 环：如果Directed Graph的一条路径从一个节点出发，又回到同一个节点，那么这条路径就形成了一个环。

5. 入度和出度：每个节点都有一个出度和一个入度，分别表示从该节点出发的指向其他节点的边的数量和指向该节点的边的数量。

6. 连通图：如果有向图中的任意两个节点之间都存在一条有向路径，那么这个有向图被称为是一个连通图。

7. 强连通图：如果一个有向图中的任意两个节点都可以互相到达，那么这个有向图被称为是一个强连通图。

8. 拓扑排序：对于一个有向无环图（DAG），可以进行拓扑排序，即将图中所有节点排列成一个线性序列，使得每个节点都排在它的所有后继节点之前。

9. 不可达节点：在Directed Graph中，有些节点可能会与其他节点没有连接，这些节点被称为是不可达节点。

10. 有向图算法：可以使用一些有向图算法，如Dijkstra算法、Floyd-Warshall算法和Bellman-Ford算法等来处理和分析有向图结构。

知識測驗

1. 在由《Game of Thrones》人物角色組成的有向圖中，找到能夠掌控七大家族的最小人物集合。

答案：使用最小割定理，將圖分為兩個部分，其中一個部分包含所有七大家族。能夠掌控七大家族的最小人物集合即為分割兩部分的最小割。

2. 假設有一個由n個節點組成的有向圖，其中每一個節點的出度和入度都是相同的，請證明如果這個圖是強連通的，則它必定存在一個哈密頓迴路。

答案：根據重頭到尾原理，將強連通的圖轉化為一個拓撲排序，必定存在一條哈密頓路徑。由於入度和出度相等，因此起點和終點相同，即存在一個哈密頓迴路。

3. 在一個城市中，有許多樓房之間互相連接，建立一個由樓房和街道組成的有向圖。每個街道上都標有一個價格，求從某一個樓房出發，到達另一個樓房的最短路徑。

答案：使用Dijkstra算法，對每個樓房進行單源最短路徑計算。從出發點開始，使用最小優先隊列來優化算法，每次選擇最短距離的節點作為下一個擴展節點，直到達到目標節點。

4. 設計一個算法，判斷給定的有向圖是否存在環。

答案：使用拓撲排序，逐步刪除入度為0的節點，如果無法找到入度為0的節點，則表明存在環。如果拓撲排序成功完成，則圖中不存在環。

5. 假設有一個由n個節點組成的有向圖，對於每一條邊<u, v>，存在一個權重w[u, v]，求一條從源點到目標點的最短路徑。

答案：使用動態規劃算法，令dist[i]為源點到i節點的最短路徑。利用之前計算出的所有點來計算下一個節點的最短路徑：dist[j] = min(dist[j], dist[i] + w[i, j])。重複計算，直到找到目標節點的最短路徑。