# 圖論(一) --- # 什麼是圖 ---- 圖是由點的集合和邊的集合所組成  --- # 點 vertex ---- 點是圖的一個基本單位，通常是圓圈 點可以連到很多條邊，也可以沒連到任何一條 點上可以有點權 --- # 邊 edge ---- 邊是圖的另一個基本單位，通常是直線或曲線 邊的頭尾都會連到一個點 ---- ## 有向邊、無向邊 邊可以分成兩種，有向邊和無向邊。 無向邊： 有向邊：  邊上可以有邊權，通常代表兩點間的距離。 ---- ## 有向圖、無向圖 所有的邊都是有向邊的圖叫有向圖， 都是無向邊的叫無向圖。 --- ## 名詞介紹 ---- ## 重邊 兩個點之間可以有不止一條邊，也可以有多條方向相同的邊，稱為重邊 ---- ## 鄰居 跟點 $v$ 直接以邊連接的點稱為 $v$ 的鄰居 ---- ## 路徑 一串相連的邊組合成的集合 路徑長是一路上的邊數和或邊權和，有可能是負的 ---- ## 環 起點和終點相同的路徑 路徑中可以包含環，因此兩點之間可能有無限多條路徑  ---- ## 自環 自環是一條起點和終點相同的邊 ---- ## 度 度代表一個點 $v$ 連接了幾條邊 出度是起點為 $v$ 的點 入度是終點點為 $v$ 的點 ---- ## 連通 圖上任兩點都有路徑可以到達稱為連通 強連通是照著圖的方向也都可以連通 弱連通則是需要把邊都變成無向邊才會連通 ---- ## 完全圖 完全圖上的每個點都連到其他全部點 ---- ## 樹和森林 樹是一個沒有環的無向連通圖 森林是數個 ---- ## 二分圖 二分圖的頂點可以分成兩組， 使得所有的邊都是跨組連接，沒有組內邊。 一張二分圖可能有多種二分的方式。 ---- ## 橋(關鍵邊) 橋在被移除之後，會導致 原本的連通塊變得不連通。 ---- ## 關鍵點 關鍵點被移除後也會使原本的連通變得不連通 橋兩端一定是關鍵點，但關鍵點不一定連到橋 --- # 圖的儲存 ---- 儲存無向邊時通常會把他拆成兩個有向邊。 邊權、兩端都跟原本一樣，只是兩個互相反向。 ---- ## 節點struct ---- 我們可以用struct來表示節點，並且 用vector存連接的節點指標，類似自製list。 如果有邊權也可以用pair綁一起。 通常不建議用。 ---- ## 邊表 ### edge list ---- 以陣列 $a[i]$ 存邊 $i$ 兩端的點和邊權。 空間用最少，但最難以點為基礎存取。 ---- ## 鄰接表 ### adjacency list ---- 以陣列 $a[i]$ 存節點 $i$ 指到的節點。 算是另類的節點法，邊權一樣可以用pair綁。 空間通常用比較小，但是沒那麼好檢查兩點之間有沒有邊， 通常在圖比較鬆散時使用。 ---- ## 鄰接矩陣 ### adjacency matrix ---- 以矩陣 $M[i][j]$ 代表節點 $i$ 指向節點 $j$ 的邊權。 優點是可以很方便的查詢兩點之間的關係。 缺點要 $N*N$ 的空間。 因為 $M[i][j]$ 只有一個，所以不支援重邊。 不過也可以自己改造。 --- # 遍歷一張圖 ---- 遍歷指的是走過一張圖的節點 有兩種主要的遍歷方法： BFS和DFS ---- ## BFS廣度優先搜尋 ---- BFS會優先搜索更廣的範圍， 會先把一層距離跑完再找下一層。 可以用來找最近的某個點。 ---- 通常以queue實作BFS 1. 將起始點放入queue 2. 拿出queue頂層，找所有它指向的未標記的點 3. 標記那些點並放入queue中 4. 重複步驟2~3直到queue空了 5. 重複步驟1~4直到標記了所有點 ---- ## 程式碼 ```cpp= void bfs(int n, const vector< vector<int> >& graph, vector< pair<int, int> >& order){ // 用&傳可以讓函式內用跟來源同一個變數，因此不會把陣列複製，而且可以修改來源給的變數 vector<bool> visited(n, false); queue<int> q; for(int start=0; start<n; ++start){ if(visited[start]) continue; // 跳過遍歷過的 visited[start] = true; order.push_back(pair<int, int>(-1, start)); q.push(start); while (!q.empty()) { int curr = q.front(); q.pop(); for (int next : graph[curr]){ //鄰接表的遍歷，其他的有不同方法 if (!visited[next]){ // 跳過遍歷過的 visited[next] = true; order.push_back(pair<int, int>(curr, next)); q.push(next); } } } } } ``` ---- ## DFS深度優先搜尋 ---- DFS會先在一條路上走下去，直到沒有可以走的再回頭找其他的。 可以用來找出口或窮舉最短路徑 ---- 方法一：類似BFS，但是用stack而不是queue 1. 將起始點放入stack 2. 拿出stack頂層，找所有它指向的未標記的點 3. 標記那些點並放入stack中 4. 回到步驟2，直到stack空了 5. 回到步驟1，直到所有點都有標記了 ---- ## 程式碼 ```cpp= void dfs(int n, const vector<vector<int>>& graph, vector<pair<int,int>>& order){ // 用&傳可以讓函式內用跟來源同一個變數，因此不會把陣列複製，而且可以修改來源給的變數 vector<bool> visited(n, false); stack<int> st; for(int start=0; start<n; ++start){ if(visited[start]) continue; // 跳過遍歷過的 visited[start] = true; order.push_back(pair<int, int>(-1, start)); st.push(start); while (!st.empty()) { int curr = st.top(); st.pop(); for (int next : graph[curr]){ //鄰接表的遍歷，其他的有不同的遍歷法 if (!visited[next]){ // 跳過遍歷過的 visited[next] = true; order.push_back(pair<int, int>(curr, next)); st.push(next); } } } } } ``` ---- 方法二：用遞迴省略stack 1. 從一個點開始 2. 找到一個它指向的沒被標記的點 3. 將那個點標記，並且也找他指向的點， 也執行步驟2 4. 當退出下一層後，回到步驟2，再找另一個點 5. 沒有點時，回到上一層 ---- ## 程式碼 ```cpp= void dfs(int curr, const vector<vector<int>>& graph, vector<pair<int,int>>& order, vector<bool>& visited){ for(int next : graph[curr]){ //鄰接表的遍歷，其他的有不同的遍歷法 if (!visited[next]){ // 跳過遍歷過的 visited[next] = true; order.push_back(pair<int, int>(curr, next)); dfs(next, graph, order, visited); } } } ``` ---- 以上三段程式碼的輸出都會有一點不同， 但是都遵守他們的概念。 而遞迴dfs是其中最好寫的， 但是遞迴過多層可能會導致錯誤。 而bfs通常都是最佔空間的