--- ###### tags: `2020 師大附中校隊培訓` --- # 基礎圖論 ## 2020 師大附中校隊培訓 #### joylintp #### 10.28.2020 --- ## 圖 ## Graph ----  一張圖由 點 (vertex/node) 和 邊 (edge) 構成 ----  無向邊: 無方向限制的邊 有向邊: 有方向限制的邊 ----  邊權: 一條邊的權重 負邊: 權重為負的邊 ----  入度: 有向圖中，指向節點的邊數 出度: 有向圖中，從節點往外指的邊數 ----  重複邊（重邊）: 起點與終點相同的兩條邊 自環: 起點與終點為同一個點的邊 ----  路徑: 從起點$u$出發到終點$v$途中經過的邊 簡單路徑: 同一條邊只經過一次的路徑 最短路徑: 從起點到終點的所有路徑中，邊權總和最小的路徑 ----  環: 起點與終點相同的路徑 負環: 權重總合小於0的環 ----  相鄰: 兩個點$u$、$v$相鄰若存在一條邊連接$u$和$v$ 連通: 兩個點$u$、$v$連通若$u$和$v$間存在一條路徑 連通塊: 節點的集合為連通塊若集合內所有的節點皆連通 --- ## 圖的種類 ----  無向圖: 所有邊皆為無向邊的圖 ----  有向圖: 所有邊皆為有向邊的圖 ----  混和圖: 同時含有無向邊和有向邊的圖 ----  簡單圖: 不含自環和重邊的圖 ----  有向無環圖(DAG): 不含環的有向圖 ----  子圖: 一張圖的子圖為其點和邊的子集合所形成的圖 ----  完全圖: 一張簡單無向圖為完全圖若其任兩點間皆恰有一條邊相連 ----  樹(tree): 任兩點之間都相通且沒有環的圖 --- ## 深度優先搜尋 ## Depth-First Search ### (DFS) ---- 到了一個節點時， 若該節點有尚未被尋訪的相鄰節點時， 優先去尋訪該節點 若所有相鄰節點都被尋訪過了， 就回到前一個節點 ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ---- ### 遞迴實作 ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; bool visit[100001]; vector<int> edge[100001]; void vis(int n) { cout << n << '\n'; visit[n] = true; } void dfs(int n) { vis(n); for (int i : edge[n]) if (!visit[i]) dfs(i); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; int a, b; while (m--) { cin >> a >> b; edge[a].push_back(b); edge[b].push_back(a); } dfs(1); return 0; } ``` --- ## 廣度優先搜尋 ## Breadth-First Search ### (BFS) ---- 到了一個節點時， 優先去尋訪所有相鄰的節點 若所有相鄰節點都被尋訪過了， 就再尋訪各相鄰節點的節點 ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ---- ### queue實作 ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; bool visit[100001]; vector<int> edge[100001]; void vis(int n) { cout << n << '\n'; visit[n] = true; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; int a, b; while (m--) { cin >> a >> b; edge[a].push_back(b); edge[b].push_back(a); } queue<int> quu; quu.push(1); while (!quu.empty()) { int now = quu.front(); quu.pop(); vis(now); for (int i : edge[now]) if (!visit[i]) quu.push(i); } return 0; } ```