# [資料結構] CH16. Undirected & Directed Graphs

* 在電腦裡面的圖有兩種，一種是**graph**，另一種是**image**。
* Graph: 具有數據的圖表，像樹狀圖一樣，是用於表達資料關係的圖形。
* Image: 圖片、照片等，用於表達真實事物的圖。
* 但其實這沒有很一定，只是要了解所謂的圖不一定就是圖片。
* 而在這裡我們要討論的就是**graph**這種資料結構。
* 一張Graph由節點(vertices)和邊(Edges)的集合所組成。
* 像是樹狀結構，但node和node之間的關係不只有父親和小孩，而是彼此之間任意連接、更加複雜的圖形。
* 樹狀結構也是一種圖。
* Graph的例子：
* 家族關係的祖譜。
* 捷運路線圖。

## Undirected & Directed Graphs
* 圖可以分為無向圖(Undirected Graphs)和有向圖(Directed Graphs)。

digraph mygraph { 
    subgraph cluster1
    {
        label = "無向圖"
        edge[arrowhead="none"]
        a[label="a"]
        b[label="b"]
        c[label="c"]
        d[label="d"]
        a -> b;
		b -> c;
		b -> d;
		d -> a;
    }	
    subgraph cluster2
    {
        label = "有向圖"
        a2[label="a"]
        b2[label="b"]
        c2[label="c"]
        d2[label="d"]
        a2 -> b2; 
		b2 -> c2;
		b2 -> d2;
		d2 -> a2;
    }
}

* 我們若說一張Graph G由set(V,E)組成，那以上圖為例，V和E分別表示成：
* $𝑉(𝐺) = \left \{a,b,c,d \right \}$
* $E(𝐺) = \left \{(a,b),(b,c),(b,d),(d,a) \right \}$
* 若是無向圖，邊的前後關係可以顛倒。
* 有向圖中，前面的點是出發點。
### 無向圖的名詞解釋
* Adjacent nodes or neighbors
* 每個邊會將兩個點相連，寫作`e=(u,v)`。
* 此時我們說點`u`和點`v`是邊`e`的**end-points**；且他們彼此為**adjacent nodes** 或 **neighbors**。
* Degree of a node
* 點`u`的degree，寫作$deg(𝑢)$，表示所有連接到`u`的邊有幾條。
* 如果`u`的degree=0，我們稱該點為**isolated node**。
* Regular graph
* 若G是一張**regular graph**，表示裡面每個點的degree都一樣。
* Path
* 從點A到點B的路徑，可表示成$P= \left \{ v_0,v_1,v_2...,v_n \right \}$，其中n為該path的長度(length)，經過的node數量等於n+1。
* Simple path
* 路徑上所有經過的點都是不同的點，該路徑稱為**simple path**。
* 例外：頭和尾可以是同一個點，即$v_0=v_n$；也就是說，path包含cycle(看下面)。
* Cycle
* 一條頭尾相同的路徑稱為**cycle**。
* **simple cycle**就是除了頭尾以外的點都不同。
* Connected graph
* 一張connected graph裡面的任意兩點$u,v$，我們都可以找到一條path從$u$走到$v$。
* Connected graph裡面不可能有isolated node。
* 若connected graph裡面沒有任何cycle，該圖是一個樹。
* Complete graph
* 所有node彼此之間都有edge連接。
* Complete graph的edge數量為$n*(n-1)/2$，其中$n$為node數量。
* Clique
* 一張graph $G=(V,E)$裡若存在clique，表示存在點集合$C \subseteq V$，且$C$裡面任意兩點都有edge連接。
* 也就是說若子圖(subgraph)為complete graph，又可以稱做clique。
* Loop
* 一條邊若兩個end-point是一樣的點，該edge稱做**loop**。
* $e=(v,v)$
* loop會讓該點的degree+2。
* Multiple edges
* 同樣的兩個點有多條邊連接，那些邊稱做**multiple edges**。
* Multi-graph
* 當graph存在loop或multiple edges，該圖為**multi-graph**。
* Size of a graph
* 一個graph的size表示裡面共有幾條edge。

### 有向圖的名詞解釋
* 其實上面的大部分也都適用於有向圖......只是有幾個要考慮方向性。
* Out-degree of a node
* Out-degree of $u$表示有幾條edge從$u$往外走。
* In-degree of a node
* In-degree of $u$表示有幾條edge從$u$往內走。
* Degree of a node
* out-degree和in-degree的加總。
* 一個loop會讓該點的out-degree和in-degree同時加一。
* Source
* 一個點若為**source**，該點的out-degree大於一，且in-degree為零。
* Sink
* 一個點若為**sink**，該點的in-degree大於一，且out-degree為零。
* Pendant vertex
* **Pendant vertex**表示degree為一的點，也被稱做**leaf vertex**。
* Reachability
* $v$ is reachable from $u$，表示能找到一條路徑從$u$到$v$。
* Parallel/Multiple edges
* 同上面的Multiple edges，但這邊連方向都要一樣。
* Strongly connected directed graph
* Strongly connected directed graph中，任意兩點$u,v$之間都有path，即使$u,v$相反也一樣。
* Weakly connected digraph
* 不管有向圖的方向性時，任意兩點$u,v$之間都有path，該圖為weakly connected digraph。
* Transitive closure
* Transitive closure的圖中，若$u$指向$v$，$u$也指向所有$v$指向的點。

digraph TransitiveClosure { 
    subgraph cluster1
    {
        label = "Graph G"
        a[label="a"]
        b[label="b"]
        c[label="c"]
        d[label="d"]
        a -> b;
		b -> c;
		c -> d;
    }	
    subgraph cluster2
    {
        label = "Transitive closure of G"
        a2[label="a"]
        b2[label="b"]
        c2[label="c"]
        d2[label="d"]
        a2 -> b2;
        a2 -> c2;
        a2 -> d2;
		b2 -> c2;
        b2 -> d2;
		c2 -> d2;
    }
}

###### tags: `DS` `note`