从存图到最短路算法的图论总结
2019-08-16 07:57:19来源:博客园 阅读 ()
从存图到最短路算法的图论总结
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
核心代码
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]);//替换
完整代码
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
原文链接:https://www.cnblogs.com/HNFOX/p/11272427.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:洛谷 P2085 最小函数值
下一篇:dfs/bfs专项训练
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash