# Graph & Tree 簡介 ## 5/31社課 --- ## Graph(圖) 在程式上用來記錄關聯性的一種方法 ---- ### 為什麼需要圖?  以人的角度觀察每筆資料間的關係很容易 在電腦中要記錄這些關係 則需要利用矩陣、串列等結構 ---- 舉一些圖的範例 ---- 紅色的點是一筆資料 白線則是表達資料間的關聯性  ---- 線條可以單向 雙向 或是連到自己 點的位置不影響圖的關係  ---- 點和線都能給權重(長度、大小等特徵) 可以用在特殊需求 ##### 數字不重要  ---- 點可以隨意命名 方便理解就好 --- 重要的是 ### 電腦如何記錄圖? ---- ### edge list 中文名"邊表" 用陣列儲存所有關係 ----  a、b代表連接的兩個點 a為起點 b為終點 | 0 | 1 | 2 | 3 | 4 | | ------- | ------- | ------- | ------- | ------- | | a:A;b:C | a:A;b:D | a:B;b:A | a:D;b:A | a:D;b:D | ---- 實作的情況 ```cpp= struct EdgeList { int a, b; //設a、b兩起始點 終點 }; Edge edge[4]; //4條線 void ex() { int p=0; //線數設為0 int x,y; while (cin >> x >> y) { edge[p].a = x; edge[p].b = y; p++; } } ``` ---- 這種方法雖然直觀 但沒辦法迅速找到我們想找的點 所以不適合計算 ---- ### adjacency matrix 名字叫"相鄰矩陣" 使用二維矩陣紀錄 ----   ---- 利用矩陣紀錄方便很多 可以順便紀錄權重、兩點間的邊數等 (點的權重要另立陣列) ---- 實作情況 ```cpp= int matrix[4][4]; //建立4點的矩陣 int point[4]; //點的權重 void adjacencymatrix() { for (int i=0; i<4; i++) for (int j=0; j<4; j++) matrix[i][j] = 0; for (int i=0; i<4; i++) cin>>point[i]; int a, b, w; //邊的起始點、終點、邊的權重 while (cin >> a >> b >> w) matrix[a][b] = w; } ``` ---- 第三種 ### adjacency lists 相鄰列表 ---- 話不多說 直接上圖   ---- 為每個點標上編號後 利用陣列、串列的方法紀錄 ---- 我比較懶 用vector ```cpp= vector<int> list[4]; void adjacency_lists() { for (int i=0; i<5; ++i) list[i].clear(); int a, b; while (cin >> a >> b) list[a].push_back(b); //讓vector自動調整該列的行數 } ``` ---- 也可以用陣列做，自己設定該列的大小 或是用Linked list 但||太麻煩以至於不想做|| 當然也可以把所有關係放到一個陣列 叫做[~~星爆氣流斬~~ 鏈式前向星](https://zh.wikiversity.org/zh/%E9%93%BE%E5%BC%8F%E5%89%8D%E5%90%91%E6%98%9F) --- ## Tree ||[這個](https://zh.wikipedia.org/zh-tw/%E6%A0%91)|| ---- 不是 是這個  ---- 一種資料結構 像是一個點連接多個點的Linked list 也可以當成每點之間只有一線的圖 ---- 如果說到排列組合 用圖解的話最先想到的是樹狀圖 樹的結構剛好適合解決這類 有先後性的情況 ---- ### 一些關於Tree的術語 ---- * 節點 node : 所有點 * 邊 edge : 所有連接的線 * 根節點 root : 樹的頂點(A點) * 葉節點 leaf : 樹的底部(E、I、G、H)  ---- * 父節點 parent : 一個點的上一層的點(單一) (比如B的父節點A) * 子結點 child : 一個點的下一層的所有點 * 祖先 ancestor : 一個點以上連接的所有點 (E的祖先B、A) * 子代 descendant : 一個點以下連接的所有點  ---- 子樹 subtree : 一個點以下連接的所有樹 (B點的子樹)  ---- 層 level : 點的位置在的層數 (比如G點在第三層) 深度 depth : 該樹到最下層的層數 (該樹有四層)  ---- 一個Tree只能有一個root 但這個root可以隨便改 如果以B點當root(移到最上面) 相關位置一樣不變(跟圖一樣性質)  ---- ### 本日練習 試著自己建adjacency lists 串列版or陣列版