欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

从存图到最短路算法的图论总结

程序员文章站 2022-04-09 15:28:46
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

(今天刚注册的博客,立刻就像写一篇博客试试,然而实际写起来才觉得没那么简单,写完后返回来以看就发现了很多缺陷,而且也不太清楚从何改起.......不过我相信写博客同样也是熟能生巧的,只要一直写下去,想必将来也能写出优秀的博客)