圖論筆記

圖論筆記

圖，由點與邊組成。

圖的種類

無向圖：可以從 u 走到 v 也能走回來。
有向圖：這條邊允許從 u 走 到 v，但不能往回走。

擁有以下特徵之一的稱為樹(Tree)

連通 且 V = E + 1。
兩點間存在唯一的簡單路徑。 (意即不可刪任意條路徑)
沒有環，但加上任意一條邊就有環。
若節點編號存在順序，除了根，每個節點都伸出一條邊連到父節點。

相關名詞

根 : 最上層的點
節點 : 储存的每筆資料
葉 : 最下層的點
父節點 : 現在節點上方直連點
子節點 : 現在節點下方連結的點
祖先 : 父節點之上的點，意旨向下dfs可以找到現在節點

存樹

以下介紹後面會使用的方法
主要是記下兩點關係，
像是 a 跟 b 相連，就讓 a 的陣列中存入 b。
利用動態陣列(vector)的特性，
只須不斷把點兩點的關係丟入。
當然也可以選擇開struct。

vector<int>tree[1024]; int main() { int n, a, b; cin >> n; while(n--) { cin >> a >> b; tree[a].emplace(b); tree[b].emplace(a); } }

遍歷樹—DFS

走一點，走到不能再走為止。
再來會回到上一點，重複動作。
以遞迴執行。

vector<int>tree[1024]; bool vis[100005]; //紀錄是否走過以避免重複走造成的無限迴圈 void dfs(int x) { vis[x] = 1; for(int i : tree[x].first) { if(!vis[i]) dfs(i); } }

遍歷—BFS

走完所有子節點，同時將該點的子節點存入queue，不斷循環。

vector<int>vec[100005]; queue <int>que; bool vis[100005]; void bfs(int x) { vis[x] = 1; que.emplace(x); while(!que.empty) { int front = que.front(); que.pop(); for(int i : vec[front]) //走完所有子節點 { if(!vis[i]) //避免鬼打牆 { vis[i] = 1, que.emplace(i); } } } }

紀錄父節點

方法是由dfs、bfs遍歷時，直接記錄下來。
下方提供dfs版

vector<int>vec[1024]; bool visable[1024]; int parent[1024]; void dfs(int x) { visable[x] = 1; for(int i:visable[x]) { if(!visable[i]) { visable[i] = 1; parent[vis[i]] = x; } } }

某點最遠點

用 dfs 特性看深度，不斷刷新最遠值。

vector<pair<int, int> >vec[1024]; bool vis[1024]; pair<int, int>far; void dfs(int x, int dis, int ord) { vis[x] = 1; for(pair<int, int> i:vec[x]) { if(!vis[i.first]) { vis[i.first] = 1; if (dis + i.second > far.second) //刷新最遠點 { far.first = x, far.second = dis; } dfs(i.first, dis + i.second); } } }

樹直徑

先找任一點的最遠點，該點的最遠點與該點將會組成樹的直徑，
也就是相離最遠的兩點。
題源TOJ 378

vector<pair<int, int> > node[100005]; pair<int, int> far[2]; bool vis[100005]; int ord; //相當於index void dfs(int x, int dis) { vis[x] = 1; for(pair<int, int> cld:node[x]) { if(!vis[cld.first]) { vis[cld.first] = 1; dis += cld.second; if(dis > far[ord].second) { far[ord].first = cld.first; far[ord].second = dis; } dfs(cld.first, dis); dis -= cld.second; } } } int main() { int m, n; cin >> m >> n; while(n--) { int a, b, cost; cin >> a >> b >> cost; node[a].push_back({b, cost}); node[b].push_back({a, cost}); } dfs(0, 0); memset(vis, 0, sizeof(vis)); ord++; dfs(far[0].first, 0); memset(vis, 0, sizeof(vis)); cout << far[1].second << "\n"; }