<style type="text/css"> .slides { text-align: left !important; } </style> # 基礎圖論 #### Author:H1de_on_bruH ---- ## 概要 圖的構成 怎麼存圖? 圖的遍歷:DFS與BFS --- ## 甚麼是圖論? ---- 維基百科: >圖論（英語：graph theory），是組合數學分支，和其他數學分支，如群論、矩陣論、拓撲學有著密切關係。圖是圖論的主要研究對象。 ---- ## 圖的組成 ---- 構成各種圖的基礎元素有節點和邊 如下圖  ---- **是的這個也算圖**  ---- 圖有分 - 有向/無向 - 連通/不連通 - 簡單/不是簡單 (無重邊和自環) - 帶權/不帶權 --- ## 圖的儲存 ---- 現在你知道甚麼是圖了 那要到底要怎麼儲存這張圖呢? ---- ### 相鄰矩陣(adjacent matrix) ---- 開一個$N\times N$的二維陣列 若有一邊從$i$連到$j$且長為$x$ 那就把$a_{i,j}$設成$x$ ---- **優點:** $O(1)$時間查找任意$x,y$間的邊的資訊,拆邊,建邊 ---- **缺點:** $O(V^2)$空間複雜度(V表節點數) 不能建重邊 ---- ### 邊表(edge list) ---- 開一個$N$的std::vector陣列 ```cpp= vector<int> adj[n] ``` 如果有一邊從$i$連到$j$ 就在`adj[i]`裡面`push_back`一個`j` ---- **優點:** $O(E)$空間複雜度(E表邊數) $O(1)$時間建邊 可以建重邊 ---- **缺點** $O(E)$拆邊,查找邊 ---- ## 圖的遍歷 ---- **怎麼走?** --- ### DFS(深度優先) ---- 找一個點開始走 一直往下找一個沒走過的點走 若且唯若你在這個點沒有連結到其他未走過的點時 回朔的上一個節點 並往另一條路走 以此類推 ```cpp= void dfs(int now) { vis[now]=1; for(int i:path[now]) if(vis[i]==0) dfs(i); } ``` ---- https://www.cs.usfca.edu/~galles/visualization/DFS.html ---- 好處：好寫+可以蓋出 dfs tree ----  ---- ### [CF:1139C - Edgy Trees ](https://codeforces.com/problemset/problem/1139/C) 給你一顆$n$個節點的樹($n$個點$n-1$個邊並且所有點相連通) 有紅邊跟黑邊 要找出有幾個長度為$k$的"好的"行程 **只要$1\le i\le k-1$中 有一個$a_i$到$a_{i+1}$($a_i$可以等於$a_{i+1}$)的簡單路徑中有經過黑色的邊就算是好的行程** ---- 總共有$n^k$種行程 現在只要再找有幾種行程不是好的就可以求出答案了 一開始建圖的時候不要把黑邊建進去 那不好的行程只剩下各個$(連通塊的大小)^k$的總和 ---- #### 其他例題 [CF:580C - Kefa and Park ](https://codeforces.com/problemset/problem/580/C) [ATC:RGB Coloring 2](https://atcoder.jp/contests/abc199/tasks/abc199_d) --- ### BFS(廣度優先) ---- 找一個點開始 把周圍的點一個一個放進"待辦清單"的最尾端 再往清單中第一個點走下去 並把他周圍還沒走到的點也放到清單的尾端 再往清單中下一個點走下去 以此類推 ```cpp= queue<int>q,q.push(1),vis[1]=1; while(q.size()) { int now=q.front(); q.pop(); for(int i:path[now]) if(!vis[i]) vis[i]=1,q.push(i); } ``` ---- https://www.cs.usfca.edu/~galles/visualization/BFS.html ---- 好處：如果從 $v$ 開始遍歷則遍歷的順序會依照 $v$ 到各個點的距離。 ---- #### [TIOJ 1572](https://tioj.ck.tp.edu.tw/problems/1572) 非常簡單的BFS裸題 比較麻煩的就是要求最小路徑中字典序最小的那條路徑 ---- 有興趣看實作的可以點下面的連結 https://pastebin.pl/view/5f91e5f6 --- ## 總結 ---- BFS跟DFS都是很基礎但都是很重要的演算法 很多演算法都是從這兩者之間演化出來的 請務必多練習多熟悉 ----