关于图论算法 - 你的小垃圾
source link: https://www.cnblogs.com/zch061023/p/16070289.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
关于图论算法
预习了一点图论的算法，记录一下：
我将分为三部分记录：
1.概念&一笔画问题
2.最短路算法
3.最小生成树算法
1st. 一笔画问题
首先明确以下几个概念：
1、欧拉通路：恰好通过图中的每条边仅一次的通路。
2、欧拉回路：是欧拉路径且起点和终点是同一个点。
3、欧拉图：存在欧拉回路的图。
关于一笔画问题的定理：
存在欧拉路的条件：图是连通的，且存在0个或2个奇点。 如果存在2个奇点，那么这两个奇点一定是这个图的起点和终点。
如果存在欧拉回路的话，就不会有奇点。
其实我们要探究的一笔画问题就是探究是否存在欧拉回路
——“问题来了，怎样求得欧拉路径呢？”
——“用DFS！”
首先确定起点和终点，也就是输入再存储这张图，记录每个点的度。然后找有没有奇点，如果有的话，就将其当成起点或终点。如果没有，就可以从任何一个点开始。
之后就用DFS找到欧拉回路就行了。不多说，直接上代码！
1 #include<iostream>
2 #define N 1001
3 using namespace std;
4 int g[N][N];//存图
5 int du[N];//记录每个点的度
6 int lu[N];//记录最后要输出的点的顺序
7 int n,cnt,e;
8 void dfs_lu(int i)
9 {
10 for(int j=1;j<=n;j++)
11 if(g[i][j]==1)
12 {
13 g[i][j]=0;
14 g[j][i]=0;
15 dfs_lu(j);
16 }
17 lu[cnt++]=i;
18 }
19 int main()
20 {
21 cin>>n>>e;
22 int x,y;
23 for(int i=1;i<=e;i++)
24 {
25 cin>>x>>y;
26 g[x][y]=1;
27 g[y][x]=1;
28 du[x]++;
29 du[y]++;
30 }
31 int start=5;//如果没有环（即没有奇点）就直接从1开始，当然从任何一个点开始都是可以的！！！
32 for(int i=1;i<=n;i++)
33 {
34 if(du[i]%2==1)
35 start=i;//记录起点
36 break;
37 }
38 cnt=0;
39 dfs_lu(start);
40 for(int i=0;i<cnt;i++)
41 {
42 cout<<lu[i]<<" ";
43 }
44 return 0;
45 }
有欧拉图，就还会有哈密顿图：
哈密尔顿通路：通过图中每个顶点仅一次的通路。
哈密尔顿回路：通过图中每个顶点仅一次的回路。
哈密尔顿图：存在哈密尔顿回路的图。
其实哈密顿图和欧拉图的区别就是一个是经过所有的边，一个是经过所有的点
其实不准确，因为只要经过所有的边，就一定会经过所有的点，但是经过所有的点不一定经过所有的边，所以他们的区别实际上是：
一个是要经过所有的点且经过所有的边，一个是经过所有的点但不用非要经过所有的边
——————————————————手动分隔线————————————————————————
2nd. 最短路问题
有四种方法，分别是：floyed算法，Dijkstra算法，Bellman-Ford算法，SPFA算法
我们明确一下这些方法各自的最优问题：
对于多源汇最短路问题，最优解是floyed算法
对于单源最短路：
如果所有边权都是正数且是一个稠密图（边数跟点数的平方是一个等级），首选朴素Dijkstra算法
如果所有边权都是正数且是一个稀疏图（边数跟点的个数是一个等级），首选堆优化版的Dijkstra算法
如果存在负权边最好使用SPFA算法
如果存在负权边且限制边数不能超过给定的数k，最好用Bellman-ford算法
1.floyed算法：
首先记录每一条边，设d[i][j]代表从i到j的最短距离，画一个图看看：
对于一整个图，我们都可以将其分解为以上的小部分，从1到3有两种选择，一种是从1到2，再从2到3，还有一种就是直接从1到3，现在我们已知每条边的边权，那就计算一下两条路径那条更短就去哪条
再比如下面的图：
显然，对于这张图，我们知道1直接到5是没有路径的，所以它们之间的最短距离d[1][5]=min(d[1][4]+d[4][5],d[1][5])=min(1+3,∞)=4
我们也可以由此得出1到6的最短路径长度，1到3的最短路径长度，因此这种方法可以实现求图上任何两点之间的最短路径长度
所以其实我认为它跟DP是有写相同之处的，比如状态转移：
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 if(d[i][k]+d[k][j]<d[i][j]){
5 d[i][j]=d[i][k]+d[k][j];
6 }
相似之处还有就是他们都需要初始化，比如它的初始化就是：
d[ i ][ i ]=0，也就是说自己到自己的距离是0
d[ i ][ j ]= 边权，i 与 j 有直接相连的边，那这条边的长度就是它的边权
d[ i ][ j ]= 0x7f，i 与 j 无直接相连的边，这条边的长度定义为一个超级大的数，只有这样我们才能筛选出最短的那条边
（当然，用memset固然简洁明了，但是在处理0和-1之外的赋值操作时会有意想不到的结果......所以还是老老实实地用循环嵌套吧！！！）
那就直接上题！
输入顶点数 m 和边数 n，任意两点的之间的距离w都<=1000，再输入p，q两点标号，接下来输入m行，每行代表一条边的起点，终点和权值，输出p，q两点之间路径长度的最小
思路就是我刚才说的，直接上代码吧！！
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 int d[101][101];
6 int main()
7 {
8 int n,m,p,q;
9 cin>>n>>m>>p>>q;
10 for(int i=1;i<=n;i++)
11 {
12 for(int j=1;j<=n;j++)
13 {
14 d[i][j]=1001;
15 }
16 }
17 //初始化将每条边变成一个很大的数
18 for(int i=1;i<=n;i++)
19 {
20 d[i][i]=0;
21 }
22 //自己到自己的长度是0
23 int i,j,len;
24 for(int ha=1;ha<=m;ha++)
25 {
26 cin>>i>>j>>len;
27 d[i][j]=len;
28 d[j][i]=len;
29 }//输入边的长度
30 for(int k=1;k<=n;k++)
31 {
32 for(int i=1;i<=n;i++)
33 {
34 for(int j=1;j<=n;j++)
35 {
36 if(d[i][k]+d[k][j]<d[i][j])
37 {
38 d[i][j]=d[i][k]+d[k][j];
39 }
40 }
41 }
42 }
43 //寻找最短距离
44 cout<<d[p][q];
45 return 0;
46 }
——————————————————手动分隔线—————————————————————
2、Bellman-Ford算法
首先明确几个概念：
什么是松弛函数？
现在有一个图，对于边集合 中任意边，
表示顶点
出发到顶点
的边的权值，而
则表示从起点
到顶点
的路径权值，
表示从顶点
到顶点
的路径。
所以松弛函数像刚才我们在讨论floyed算法是所做的操作一样：
若存在边 ，使得：
则更新 值：
其实就是更新成较短的路径的长度呗，这就是三角变换
初始化的操作也是一样的：
现在我们将对边集合 中每条边都执行一次松弛视为一次迭代操作，现在我们来看迭代次数和图之间的关系（至于为啥要这样以后会说的）
那我们其实不难发现，在一个图中，有时只使用一次松弛操作就可以实现找到最优解，比如下面这张图：
对边 执行松弛函数，则
对边 执行松弛函数，则
对边 执行松弛函数，则
那我们只要通过一次迭代操作就可以得到最优解了！
BUT！
如果我的运气很不好，（实际上是最坏），那一次就解决问题的概率其实不大，所以我至少要进行三次操作（由于过程太麻烦，这里就不过多赘叙）
那么发现规律：
最多要进行m（顶点数）-1 次操作，就能让所有的点确定，
即对于未确定的顶点，每次对边集进行一次操作，都至少会增加一个确定的点！
首先进行第一次迭代，那么b点一定会被确定，因为b只能从a点过去。
在第二次迭代的时候，由于我们确定了b点和a点，要不就是从a到b到c，要不就是直接从a到c 所以与a，b构成三角形的点c一定会被确定。
下面依次类推，都至少会确定一个点，证毕。
但是我们要有一点前提：
就是不能允许负权回路出现，因为如果有负权回路，那么这个最短路就会一直被更新（一直减减减），那就无法在 m-1 次操作内运行出来
（介绍一下啥是负权回路：一个回路上所有边权相加小于零）
因此Bellman-Ford算法就有了另一个作用：
判断图中是否有负权回路出现
——————————————————手动分割线——————————————————
三、SPFA
思想跟Bellman-Ford算法其实几乎一样，唯一的区别就是人家更牛了！！！
由于我不知道Bellman-Ford要进行多少次迭代，所以要试m-1次，那就很不好，所以SPFA就成功地解决了这个问题：
初始时我们将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时，也就是没法再修改的时候，算法结束。
代码实现：
1 d = ∞，让队列Q初始化为空
2 d[S]=0，Q.in(S)//让起点入队
3 while(!Q.empty())
4 {
5 u=Q.out();//让他出队
6 for(所有的边w(u,v))
7 if(d[v]>d[u]+len(u,v))//让牵扯到的点全都进队
8 {
9 d[v]=d[u]+len(u,v);
10 if(v不在队内) Q.in(v);
11 }
12 }
所以其实他的特点就和BFS挺像，不同的是：
BFS每个点只能遍历一次，但是SPFA可以让某些点在队里队外反复横跳（来回进出）
——————————————————手动分隔线————————————————————————
四、Dijkstra算法
设起点为s，dis[v]表示从起点s到点v的最短路径，path[v]表示v的前驱结点（便于最后输出路径）
首先初始化：dis[v]等于正无穷（或是一个超大的数），dis[s]等于0（其实任何一个结点到自己的距离都初始化为0），path[s]=0（也就是起点没有前驱）
然后在所有点中找到dis最短的（即到原点距离最近的），并将其标记成已经确定的最短路径。（这里视作u）
接着通过for循环找到所有与u相连的、未被确定为最短路径的点v，通过三角变换，更新新的路径：
1 if(dis[u]+w[u][v]<dis[v])
2 {
3 dis[v]=dis[u]+w[u][v];//进行更新
4 path[v]=u;//记录前驱
5 }
但是用这玩意有个前提：没有负权边（很好理解对吧）
完整代码：
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 const int maxn=101;
6 int judge[maxn];//记录这个点是否已经用过了
7 int a[maxn][maxn];//表示两个点之间的距离
8 int dis[maxn];//到起点的距离
9 int path[maxn];//前驱
10 int n,m,start;
11 const int chaojida=99999;
12 void init()//准备操作
13 {
14 cin>>n>>m>>start;
15 int x,y,len;
16 for(int i=1;i<=n;i++)
17 {
18 for(int j=1;j<=n;j++)
19 {
20 if(j==i) a[i][j]=0;
21 else a[i][j]=chaojida;
22 }
23 }
24 //第一步：初始化
25 //将所有的距离（出自己以外）都设为一个超级大的数，自己到自己的距离是0
26 for(int i=1;i<=m;i++)
27 {
28 cin>>x>>y>>len;
29 a[x][y]=len;
30 a[y][x]=len;
31 }
32 //读取输入的信息，用给出的条件（起点，终点和距离）更新原始数组
33 }
34 void dijkstra(int s)
35 {
36 for(int i=1;i<=n;i++)
37 {
38 dis[i]=chaojida;//目前，每个点到起点的距离都超级大
39 judge[i]=false;//都还没被用过
40 }//初始化
41 dis[s]=0;//还是初始化（起点到自己的距离是0
42 for (int i=1;i<=n;i++)
43 {
44 int mind=chaojida;
45 int k;//用来记录准备放入集合1的点
46 for(int j=1;j<=n;j++) //查找集合2中d[]最小的点
47 {
48 if((!judge[j])&&(dis[j]<mind))
49 {
50 mind=dis[j];//更新最小值，以供后面比较
51 k=j;//最小的点是k
52 }
53 if(mind==chaojida)
54 {
55 break; //更新结点求完了
56 }
57 judge[k]=true;
58 }// 加入集合1
59 for(int j=1;j<=n;j++) //修改集合2中的d[j]
60 {
61 if((!judge[j])&&(dis[k]+a[k][j]<dis[j]))
62 {
63 dis[j]=dis[k]+a[k][j];
64 path[j]=k;
65 }
66 }
67 }
68 }
69 void search(int x)
70 {
71 if(x!=start)
72 {
73 search(path[x]);
74 }
75 cout<<x<<' ';
76 }//便于最后输出前缀
77 void write()
78 {
79 cout<<start<<"到其余各点的最短距离是："<<endl;
80 for(int i=1;i<=n;i++)
81 {
82 if(i!=start)
83 {
84 if(dis[i]==chaojida) cout<<i<<"不可达！"<<endl;
85 else
86 {
87 cout<<i<<"的最短距离："<<dis[i] <<",依次经过的点是：";
88 search(path[i]);
89 cout<<i<<endl;
90 }
91 }
92 }
93 }//输出应题目要求
94 int main()
95 {
96 init();
97 dijkstra(start);
98 write();
99 return 0;
100 }
正好凑成一百行！！！
————————————————————纯手动分隔线——————————————————————
3rd. 最小生成树算法
众所周知，有N个点，用N-1条边连将所有的点连接成一个连通块，形成的图形只可能是树，没有别的可能。（哈哈哈，这就不用解释了吧）
所以我们就引出了最小生成树的概念：
有一个n个点的图，这个图有至少n-1条变。现在要从里面挑出n-1条边，使其连接所有的点，而且这些边权之和是最小的，这就是最小生成树。
一. Prim算法
我们可以通过染色的方式跟好的理解一下：
初始时我们将所有点都染成蓝色（蓝色代表还没有被选中，白色代表已经被选入生成的树中），我们每次都会将一个点选入最小生成树，这个点有以下几个前提：
1.未被选中过、2.与上一个选中的点相连且边权是上一个点连接的所有边中最短的。
这样一直选，直到所有的点都被选中为止
算法描述：
以1为起点生成最小生成树，min[v]表示蓝点v与白点相连的最小边权。
MST表示最小生成树的权值之和。
a）初始化：min[v]= ∞(v≠1); min[1]=0;MST=0;
b）for (i = 1; i<= n; i++)
1.寻找min[u]最小的蓝点u。
2.将u标记为白点
3.MST+=min[u]
4.for 与白点u相连的所有蓝点v
if (w[u][v]<min[v])
min[v]=w[u][v];
c）算法结束： MST即为最小生成树的权值之和
代码实现：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 int juzhen[101][101]; //邻接矩阵
6 int minn[101]; //minn[i]存放蓝点i与白点相连的最小边权
7 bool judge[101];
8 //judge[i]=True，表示顶点i还未加入到生成树中
9 //judge[i]=False，表示顶点i已加入到生成树中
10 int n,i,j;
11 int main()
12 {
13 cin>>n;
14 for(i=1;i<=n;i++)
15 {
16 for(j=1;j<=n;j++)
17 {
18 cin>>juzhen[i][j];
19 }
20 }
21 memset(minn,0x7f,sizeof(minn)); //初始化为maxint
22 minn[1]=0;
23 memset(judge,1,sizeof(judge));//初始化为True，表示所有顶点为蓝点
24 for(i=1;i<=n;i++)
25 {
26 int k=0;
27 for(j=1;j=n;j++) //找一个与白点相连的权值最小的蓝点k
28 {
29 if(judge[j]&&(minn[j]<minn[k]))
30 {
31 k=j;
32 }
33 }
34 judge[k]=false; //蓝点k加入生成树，标记为白点
35 for(j=1;j<=n;j++) //修改与k相连的所有蓝点
36 {
37 if(judge[j]&&(juzhen[k][j]<minn[j]))
38 {
39 minn[j]=juzhen[k][j];
40 }
41 }
42 }
43 int sum=0;
44 for(i=1;i<=n;i++) //累加权值
45 {
46 sum+=minn[i];
47 }
48 cout<<sum;
49 return 0;
50 }
_______________________________纯手动分隔线——————————————————————
最后一个算法：
二、Kruskal算法
（Tips：需要了解并查集算法，可自行去看下一个博客——并查集）
Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。
当然，体现并查集思想的地方就是首先将每一个点看作一个集合，再将选中的那条边的两个顶点合并成一个集合，下次的找遍的时边时候判断边的两个顶点是不是在集合里就行了。
算法描述:
1、初始化并查集。father[x]=x。
2、tot=0
3、将所有边用快排从小到大排序。
4、计数器 k=0;
5、for(i=1; i<=M; i++) //循环所有已从小到大排序的边
if 这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)
begin
①合并u,v所在的集合，相当于把边(u,v)加入最小生成树。
②tot=tot+W(u,v)
④如果k=n-1,说明最小生成树已经生成，则break;
6. 结束，tot即为最小生成树的总权值之和。
代码实现：
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边
6 int fat[10001];//记录集体老大
7 struct node
8 {
9 int from,to,dis;//结构体储存边 (起点，终点，边权）
10 }edge[10001];
11 bool cmp(const node &a,const node &b)//sort排序
12 {
13 return a.dis<b.dis;
14 }
15 int father(int x)//并查集的一部分 ，查找两个元素他们的老大是不是一样的
16 //（具体并查集内容可见下一个博客----并查集 ）
17 {
18 if(fat[x]!=x)
19 return father(fat[x]);
20 else return x;
21 }
22 void unionn(int x,int y)//加入团体，并查集的一部分
23 {
24 fat[father(y)]=father(x);
25 }
26 int main()
27 {
28 scanf("%d%d",&n,&m);//输入点数，边数
29 for(int i=1;i<=m;i++)
30 {
31 scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息
32 }
33 for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 （初始化）
34 sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现）
35 for(int i=1;i<=m;i++)//从小到大遍历
36 {
37 if(k==n-1) break;//n个点需要n-1条边连接
38 if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体
39 {
40 unionn(edge[i].from,edge[i].to);//加入
41 tot+=edge[i].dis;//记录边权
42 k++;//已连接边数+1
43 }
44 }
45 printf("%d",tot);
46 return 0;
47 }
代码那么那么详细，我就不解释了
就先记录到这吧，以后还会加一些题之类的，会日臻完善
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK