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)

想自殺才自己寫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.1 BFS

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

如果我們從 A 開始做 BFS，我們可以得到：

  • 和 A 在同一個 connected component 中的最短路徑
  • 找出兩個 vertex 之間的可能路徑

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

時間複雜度: \(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’s.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

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

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

以下是 Pseudo code

  • 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)}

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

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

  1. 接著第四個取出來的 edge(1,2). 因為 vertex 1, 2 分屬不同的 set, 故將此 edge 加到 A
Set A { (0, 5), (2, 3), (1, 6), (1, 2)}

  1. 接著第五個取出來的 edge(3, 6). 因為 vertex 3, 6 屬於同一個 set, 故捨棄此 edge! 
Set A { (0, 5), (2, 3), (1, 6), (1, 2)}

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

  1. 第八個取出來的 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

Select a repo