INTRODUCTION: 圖論演算法在電腦科學中扮演著很重要的角色，它提供了對很多問題都有效的一種簡單而系統的建模方式。很多問題都可以轉化為圖論問題，然後用圖論的基本演算法加以解決。--百度百科 對於OI而言，圖是指由若幹給定的點及若幹條連接兩點的線(邊)所構成的圖形 藉助圖論知識，我們往往可以將一 ...
INTRODUCTION:
圖論演算法在電腦科學中扮演著很重要的角色，它提供了對很多問題都有效的一種簡單而系統的建模方式。很多問題都可以轉化為圖論問題，然後用圖論的基本演算法加以解決。--百度百科
對於OI而言，圖是指由若幹給定的點及若幹條連接兩點的線(邊)所構成的圖形
藉助圖論知識，我們往往可以將一些複雜的問題轉化到基礎的圖論演算法上，進而使用已有演算法解決全新問題
那麼想如果想要運用圖論，首先要從存圖開始
前排感謝教我圖論的周潤喵老師，syc學長，就序老師
可是我還是沒學會
一，存圖
對於一個圖而言，它可以根據便是否有反向分成兩類：有向圖與無向圖，
不過二者的存圖方式大同小異，以下以有向圖為例；
1，鄰接矩陣（Adjacency matrix）
鄰接矩陣作為一種簡潔實用的存圖方式，具有簡單可靠的優勢，一般不太會打錯，但是他的空間複雜度高達O(n^2),使得他的使用相當受局限
不過，在數據範圍比較小或者想要打暴力部分分的時候，鄰接矩陣還是具有相當大的優勢的。
（比如說鄰接矩陣+Floyd打暴力）
在鄰接矩陣中，我們用e[i][j]表示點i到點j的距離（也就是邊i->j的邊權）
1 const int INF = 9999999999;//設一個較大的數為無窮大 2 int n, m;//n為點數，m為邊數 3 int e[5005][5005];//貌似開5005*5005就快MLE了...所以要謹慎一點 4 for (int i = 1; i <= n; i++) 5 for (int j = 1; j <= n; j++) 6 if (i == j) 7 e[i][j] = 0;//我自己到我自己的距離當然是0 8 else 9 e[i][j] = INF;//一開始還沒有邊，所以我到其他人的距離先設為無窮大 10 for (int i = 1; i <= m; i++)//讀入邊 11 { 12 int from, to, weight;//從哪來，到哪去，路多長 13 cin >> from >> to >> weight; 14 e[from][to] = weight;//無向圖存兩遍 15 e[to][from] = weight;//from到to的距離和to到from的距離是相等的 16 }
個人認為鄰接矩陣是一種比較可靠的存圖方式，在數據較小的時候一般不會出錯，
不過在使用時一定要根據題目含義對有向圖，無向圖或重邊，自環，等特殊情況進行判斷，以免出錯。
2，鄰接表（Adjacency table）
觀察之前的鄰接矩陣，我們可以看出，當存在很多個點（假設有n個），但邊的數量（m）卻遠小於n2時，矩陣中很多的空間都沒有用到，存在著極大的空間浪費
這使得鄰接矩陣無法應付n>=10000(甚至更大)的情況，然而這種在OI里是很常見的，所以我們就要引入一種OI里最常見（總之我覺得挺常見的）
的存圖方式：鄰接表
首先，鄰接表本質上是一種鏈表，表中的每一個節點使用指針或模擬指針進行連接（其實是不連著的）
同時，鄰接表不同於鄰接矩陣，他是以邊為單位進行存儲的，所以他所占的空間完全由邊的數量決定，和點的數量沒什麼關係，
他無論在空間還是時間上都相當優秀，在OI中一般情況下不會出現連鄰接矩陣都存不下的圖（至少本蒟蒻沒見過）
1 #include<iostream> 2 using namespace std; 3 struct edge 4 { 5 int from; 6 int to; 7 int next;//模擬指針 8 int weight; 9 }e[2000080];//看吧，他開很大都不會爆，不過要註意無向圖開兩倍 10 //畢竟一條無向邊其實是當作兩條有向邊存的 11 int head[50005];//head[i]表示點i所發出的第一條邊的數組下標 12 int tot;//邊的總數 13 int n, m; 14 void add(int from,int to,int weight) 15 { 16 tot++; 17 e[tot].from = from; 18 e[tot].to = to; 19 e[tot].weight = weight; 20 e[tot].next = head[from]; 21 head[from] = tot; 22 }//加邊的模板 23 int main() 24 { 25 cin >> n >> m; 26 for (int i = 1; i <= m; i++) 27 { 28 int x, y, z; 29 cin >> x >> y >> z; 30 add(x, y, z); 31 add(y, x, z);//依然無向邊存兩次 32 } 33 for (int i = head[1]; i; i = e[i].next) 34 //遍歷該點上所有的邊，如果沒有下一條了（i=0），我就停 35 //如果還有下一條邊，我就繼續往後遍歷（i=e[i].next） 36 cout << e[i].to; 37 //貌似沒解釋清楚，感性理解一下？ 38 return 0; 39 }
3，vector存圖
利用stl庫中提供的動態數組vector存圖，時空上的效率都和鄰接表差不多（據說開了OI優化會稍微快一點）
註意要開<vector>頭文件
#include<iostream> #include<vector> #include<algorithm> using namespace std; struct edge { int from; int to; int weight; }; vector<edge> e[100086];//e[i][j]表示點i的第j條邊 //貌似比鄰接表稍微簡單一點 int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { edge t;//定義一條新的的邊出來 int x, y, z; cin >> x >> y >> z; t.from = x; t.to = y; t.weight; e[x].push_back(t);//把他塞進去 t.from = y; t.to = x; e[y].push_back(t);//改一改，反向塞進去 } for (int i = 0; i < e[1].size(); i++) //查詢很方便 //不過註意vector是從0開始的 cout << e[1][i].to; return 0; }
存圖時的坑點：
-
重邊：比較一下他和原本的那條邊那個權值更小，選更小的存
-
自環：對於一般的題貌似可以直接不管他
-
無向圖沒開兩倍：二話不說直接RE
二，最短路
常見的最短路演算法主要有三類：
Floyd，Dijkstra以及Bellman Ford
當然還有他們的優化，以及一些其他的演算法，不過貌似那些都有很多限制條件，只能在一些特定情況下只用
1，Floyd
這個演算法實在太著名了，因為他的核心代碼只有5行....
1 for (int k = 1; k <= n; k++)//枚舉中間點 2 for (int i = 1; i <= n; i++)//枚舉起點 3 for (int j = 1; j <= n; j++)//枚舉終點 4 e[i][j] = min(e[i][j], e[i][k] + e[k][j]);//替換
大概就是說，從i點到j點是直接走比較近還是從i到k再從k到j這樣繞一圈比較近，如果我繞一圈近的話就更新一下路徑長度
完整代碼
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 int e[1000][1000]; 6 int main() 7 { 8 int n, m; 9 cin >> n >> m; 10 for (int i = 1; i <= n; i++) 11 for (int j = 1; j <= m; j++) 12 if (i == j) 13 e[i][j] = 0; 14 else 15 e[i][j] = 9999999; 16 for (int i = 1; i <= m; i++) 17 { 18 int x, y, z; 19 cin >> x >> y >> z; 20 e[x][y] = z; 21 e[y][z] = z; 22 } 23 for (int k = 1; k <= n; k++)//枚舉中間點 24 for (int i = 1; i <= n; i++)//枚舉起點 25 for (int j = 1; j <= n; j++)//枚舉終點 26 e[i][j] = min(e[i][j], e[i][k] + e[k][j]);//替換 27 return 0; 28 }
演算法優點：
-
他求的是多源最短路，也就是說跑完一次Floyd，那麼圖中任意兩個點之間的最短路就都知道了，不像後兩種求的是單源最短路
-
好打
演算法缺點：
-
太慢了.....時間複雜度O(n3)
2，Dijkstra
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const long inf = 20041001; 5 int n; 6 int m; 7 int s; 8 int tot; 9 struct edge 10 { 11 long weight; 12 int to; 13 int next; 14 }e[500005]; 15 struct node 16 { 17 int head; 18 }no[10086]; 19 long long dis[10086]; 20 bool book[10086]; 21 void add(int from, int to, int weight) 22 { 23 tot++; 24 e[tot].to = to; 25 e[tot].weight = weight; 26 e[tot].next = no[from].head; 27 no[from].head = tot; 28 } 29 int main() 30 { 31 cin >> n >> m >> s; 32 book[s] = 1; 33 for (int i = 1; i <= n; i++) 34 dis[i] = inf; 35 dis[s] = 0; 36 for (int i = 1; i <= m; i++) 37 { 38 int x, y, w; 39 cin >> x >> y >> w; 40 if (x != y) 41 add(x, y, w); 42 } 43 for (int i = no[s].head; i; i = e[i].next) 44 { 45 if (e[i].weight < dis[e[i].to]) 46 dis[e[i].to] = e[i].weight; 47 } 48 for (int i = 1; i < n; i++) 49 { 50 int u = 0; 51 int minn = inf; 52 for (int j = 1; j <= n; j++) 53 { 54 if (book[j] == 0 && dis[j] < minn) 55 { 56 minn = dis[j]; 57 u = j; 58 } 59 } 60 book[u] = 1; 61 for (int i = no[u].head; i; i = e[i].next) 62 { 63 if (dis[e[i].to] > dis[u] + e[i].weight) 64 dis[e[i].to] = dis[u] + e[i].weight; 65 } 66 } 67 for (int i = 1; i <= n; i++) 68 cout << dis[i] << " "; 69 return 0; 70 }
演算法優點
-
快了不少，好歹達到了O(n2)的複雜度，用堆兒優化之後甚至可以達到O((n+m)logn),算是比較優秀了
演算法缺點
-
求的是單源最短路，也就是說我每次求完都只能知道點s到各個點的最短距離，如果我要求每個點的，也就要跑n次，就很慢了
-
關鍵是他處理不了負權邊，尤其是負權迴路
3，Bellman Ford
1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include<vector> 5 #include<map> 6 #include<bitset> 7 #include<set> 8 #include<string> 9 #if !defined(_WIN32) 10 #include<bits/stdc++.h> 11 #endif // !defined(_WIN32) 12 #define ll long long 13 #define dd double 14 using namespace std; 15 int t; 16 int n, m, w; 17 int tot; 18 struct edge 19 { 20 int from; 21 int to; 22 int weight; 23 }e[100086]; 24 int dis[5005]; 25 void add(int x, int y, int z) 26 { 27 tot++; 28 e[tot].from = x; 29 e[tot].to = y; 30 e[tot].weight = z; 31 } 32 bool Bellman_Ford() 33 { 34 memset(dis, 0x3f3f3f3f, sizeof(dis)); 35 dis[1] = 0; 36 for (int i = 1; i < n; i++) 37 { 38 for (int j = 1; j <= tot; j++) 39 { 40 if (dis[e[j].to] > dis[e[j].from] + e[j].weight) 41 dis[e[j].to] = dis[e[j].from] + e[j].weight; 42 } 43 } 44 for (int i = 1; i <= tot; i++) 45 if (dis[e[i].to] > dis[e[i].from] + e[i].weight) 46 return 0; 47 return 1; 48 } 49 int main() 50 { 51 cin >> t; 52 while (t--) 53 { 54 tot = 0; 55 memset(e, 0, sizeof(e)); 56 memset(dis, 0, sizeof(dis)); 57 n = 0, m = 0, w = 0; 58 cin >> n >> m >> w; 59 for (int i = 1; i <= m; i++) 60 { 61 int x, y, z; 62 cin >> x >> y >> z; 63 add(x, y, z); 64 add(y, x, z); 65 } 66 for (int i = 1; i <= w; i++) 67 { 68 int x, y, z; 69 cin >> x >> y >> z; 70 add(x, y, 0 - z); 71 } 72 if (Bellman_Ford()) 73 cout << "NO" << endl; 74 else 75 cout << "YES" << endl; 76 } 77 return 0; 78 }
演算法優點
-
可以處理負權，如果有負權迴路，則可以把他判斷出來
演算法缺點
-
很慢，時間複雜度O(nm),而且求的是單元最短路，一般只用來判斷是否有負權迴路，而且實際使用時往往要使用他的隊列優化，也就是SPFA
（今天剛註冊的博客，立刻就像寫一篇博客試試，然而實際寫起來才覺得沒那麼簡單，寫完後返回來以看就發現了很多缺陷，而且也不太清楚從何改起.......不過我相信寫博客同樣也是熟能生巧的，只要一直寫下去，想必將來也能寫出優秀的博客）
