# Graph 圖形

* explore a graph

Such like we want to find the path between two nodes in the grpah.

## 1. Definition
#### Recall graph G = (V, E)
* V = set of vertices (arbitrary labels)
* E = set of edges i.e. vertex pairs (v, w)
* ordered pair ⇒ directed edge of grap 有向圖
* unordered pair ⇒ undirected 無向圖


* Self loop and self edge is not permittrd


#### Degree
* Degree of vertex v:
* **undriected graph**
* the number of edges incident to v.
* **driected graph**
* In-dgree: The number for which vertex is a head.
* Out-dgree: The number for which vertex is a tail.
* Degree of driected graph is v = in-degree + out-degree

##### How can a graph do ?

- web crawling
- social networking 社群網路之間的關係
- network broadcast
- garbage collection ??
- model checking (有限狀態機驗證)

### Pocket Cube
舉個例子 2x2 的魔術方塊

#### Configuration graph:

- vertex for each possible state
- edge for each basic move (e.g., 90 degree turn) from one state to another

## 2. Graph Imperment

### 2.1. Adjacency List


**優點**
* 適合儲存頂點數多、但邊數很少的圖形
* 能較彈性地使用記憶體，**絕對要用vector or list 做** <= 想不開才用Linked List
* 求圖形上的邊數、判斷是否為連通圖、判斷有無Cycle形成，僅需 O(n+e) 時間

**缺點**
* 對於經常要判斷邊是否存在的問題，複雜度為 O(e)

:::danger
想自殺才自己寫Linked List
:::

以下是 AdjList 的範例 code ：

class Graph {
private:
    int num_vertex;
    std::vector<int> AdjList;
    
    void DFSUtil(int v, bool visited[]); 
public:
    
    Graph():num_vertex(0){};             // construct class with no function parameter, then the vertex will be set to 0
    Graph(int N):num_vertex(N){         //construct class with number of vertex
        AdjList.resize(num_vertex);     //initialize Adjlist
    }

    void AddEdgeList(int from, int to){
        AdjList[from].push_back(to);
    }

};

### 2.2. Adjacency Matrix

**優點**

* 判斷邊 (i, j) 是否存在 => O(1)
* 適合儲存邊數非常多的圖形

**缺點**
* 當圖形上的頂點數很多、邊數很少時，會形成稀疏矩陣 (sparse matrix)，浪費記憶體空間

## 3. Graph Search

### 3.1 BFS

考慮這張圖，這邊先用 Adjacency List 來做做看。
先發現這是一張 connected undirected graph , 所以我們可以確保任一個 vertex 都至少有一條 edge 與其他 vertex 連接。

如果我們從 **A** 開始做 **BFS**，我們可以得到：
* 和 A 在同一個 connected component 中的**最短路徑**
* 找出兩個 vertex 之間的**可能路徑**

:::info
Since Graph G is a connected undriected graph, so we can always find the path that connected any two vertexs in this grpah.
:::

我們看看下面這個步驟圖


影片連結：https://www.youtube.com/watch?time_continue=350&v=0u78hx-66Xk&feature=emb_logo

Code: https://gitlab.parto.nctu.me/kerwin/code_practice/blob/master/DS/DS/Grpah/Graph_traversal/undirected_graph.cpp

如果我們拿一顆 tree 當做例子，我們可以了解到，BFS 就是 Level-order，而 tree 本身就是一個特殊的圖。


### 3.2 DFS

* 從哪個vertex開始不重要, edge順序也不重要

### 3.3 Connected Component
## 4 Shortest Path

### 4.1 Dijkstra's Algorithm
:::info
時間複雜度: $O(VlogV+E)$
:::

對一個 grpah G = {E, V}
重複下面這件事 V 次，以將所有點加入到最短路徑樹
* 尋找一個目前不在最短路徑樹上而且離**起點**最近的點：
* 將此點加入到最短路徑樹之中
*

在實作上我們可以利用 priority_queu 去讓每次在queu 裡面的第一個都是與起點距離最近的 vertex 也就是我們下一次要找pick 的 vertex 。

void Graph::dijkstra(int start){
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
    
    vector<int> dist{_num_vertex, INF};    // distances as infinite (INF) 
    
    //set the first vertex to be 0
    pq.push(make_pair(0, start));
    dist[start] = 0;

    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        
        for(vector< pair<int, int> >::iterator i = _AdjList[u].begin(); i != _AdjList[u].end(); ++i){
            int v = (*i).first;
            int weight = (*i).second;
        
            if(dist[v] > dist[u] + weight){
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[u], v));
            }
        }
    }
    printf("Vertex   Distance from Source\n"); 
    for (int i = 0; i < _num_vertex; ++i) 
        printf("%d \t\t %d\n", i, dist[i]); 
}

Code: https://gitlab.parto.nctu.me/kerwin/code_practice/blob/master/DS/DS/Grpah/Shortest_Path/Dijkstra%E2%80%99s.cpp

### 4.2 Bellman-Ford
影片連結： https://www.youtube.com/watch?v=5GT5hYzjNoo

## 5. Spanning Tree

* Give a **connected** and **undriected** graph, that is the **subgraph** that is a tree connect **all the vertices in the graph**.

### 5.1 Min (Max) spanning tree
* The spanning tree of the graph, whose the sum of weight is min (max).

為了要解決最小(大)生成樹問題，我們有這邊使用三種演算法，Kruskal and Prim，兩種演算法均為Greedy algorithm
### 5.2 Kruskal’s algorithm

:::info
* 平均時間複雜度: $O(E logV)$ $E$和$V$分別是圖的邊集和點集。
* 最壞時間複雜度: $Ω(|E|+|V|)$
:::

一般來說，我們在實作 Kruskal’s algorithm 的時候，我們會利用 Dijont Set 去判斷是否產生 loop

<font color=red>**以下是 Pseudo code**</font>

* MAKE-SET(v): 創造一個set 包含 v.
* FIND-SET(v): 找到set 包含 v.
* UNION(u,v): 把兩個set合併起來

MST-KRUSKAL(G,w)  
A={}  
for each vertex v∈G.V  
    MAKE-SET(v)  
sort G.E by w  
for each edge (u,v) ∈G.E  
    if FIND-SET(u)≠FIND-SET(v)  
        A=A⋃{(u,v)}  
        UNION(u,v)  
return A   

首先我們先來看看這張圖


我們先創建一個 set 包含所有的 edges and vertices in G = {E, V}.
我們先 sort 過所有的 edges 得到

[10, 12, 14, 16, 18, 22, 24, 25, 28]

以及

Set A {()}

1. 所以第一個被抓出來的 edge 是 edge(0,5). 因為 vertex 0, 5 分屬不同的 set, 故將此 edge 加到 A

Set A { (0,5)}


2. 接著第二個取出來的 edge(2,3). 因為 vertex 2, 3 分屬不同的 set, 故將此 edge 加到 A

Set A { (0, 5), (2, 3) }


3. 接著第三個取出來的 edge(1,6). 因為 vertex 1, 6 分屬不同的 set, 故將此 edge 加到 A

Set A { (0, 5), (2, 3), (1,6)}


4. 接著第四個取出來的 edge(1,2). 因為 vertex 1, 2 分屬不同的 set, 故將此 edge 加到 A

Set A { (0, 5), (2, 3), (1, 6), (1, 2)}


5. 接著第五個取出來的 edge(3, 6).<font color="red"> 因為 vertex 3, 6 屬於同一個 set, 故捨棄此 edge! </font>

Set A { (0, 5), (2, 3), (1, 6), (1, 2)}


6. 然後繼續弄直到
7. 第七個取出來的 edge(4,6). 因為 vertex 4, 6 屬於同一個 set {(1,2), (1,6), (2,3), (3,4)}, 故捨棄此 edge!


8. 第八個取出來的 edge(4,5). 因為 vertex 4, 5 分屬不同的 set, 故將此 edge 加到 A; 且此時 A 有 6 個 edges = |V|-1. 故 MST 已經完成!

Set A { (0, 5), (2, 3), (1, 6), (1, 2), (3, 4), (4, 5)}


然後我們來看看他的證明

http://www.m98.nthu.edu.tw/~s9822506/Kruskal.pdf

### 5.3 Prim's Algorithm

* 屢次找尋不在樹上，且**離樹最近**的點
* 無論從哪個出發都會得到一顆相同的樹

與 Dijkstra's Algorithm 類似，都是透過窮舉去尋找樹上得點，只是 Dijkstra 是找不在樹上，且**離根最近**的點


5.4 Soll