关于图论算法

预习了一点图论的算法，记录一下：

我将分为三部分记录：

1.概念&一笔画问题

2.最短路算法

3.最小生成树算法

一、一笔画问题

首先明确以下几个概念：

1、欧拉通路：恰好通过图中的每条边仅一次的通路。

2、欧拉回路：是欧拉路径且起点和终点是同一个点。

3、欧拉图：存在欧拉回路的图。

关于一笔画问题的定理：

　　存在欧拉路的条件：图是连通的，且存在0个或2个奇点。 如果存在2个奇点，那么这两个奇点一定是这个图的起点和终点。

 　　如果存在欧拉回路的话，就不会有奇点。

其实我们要探究的一笔画问题就是探究是否存在欧拉回路

——“问题来了，怎样求得欧拉路径呢？”

——“用DFS！”

首先确定起点和终点，也就是输入再存储这张图，记录每个点的度。然后找有没有奇点，如果有的话，就将其当成起点或终点。如果没有，就可以从任何一个点开始。

之后就用DFS找到欧拉回路就行了。不多说，直接上代码！

 1 #include
 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)
41     {
42         cout<" ";
43     }
44     return 0;
45 }

有欧拉图，就还会有哈密顿图：

定义：

哈密尔顿通路：通过图中每个顶点仅一次的通路。

哈密尔顿回路：通过图中每个顶点仅一次的回路。

哈密尔顿图：存在哈密尔顿回路的图。

其实哈密顿图和欧拉图的区别就是一个是经过所有的边，一个是经过所有的点

其实不准确，因为只要经过所有的边，就一定会经过所有的点，但是经过所有的点不一定经过所有的边，所以他们的区别实际上是：

一个是要经过所有的点且经过所有的边，一个是经过所有的点但不用非要经过所有的边

——————————————————手动分隔线————————————————————————

二、最短路问题

有四种方法，分别是：floyed算法，Dijkstra算法，Bellman-Ford算法，SPFA算法

首先明确一些概念：

首先最短路是啥意思我就不说了，至于问题分类，主要分为两类：

一类是求从某个顶点（源点）到其它顶点（终点）的最短路径（dijkstra算法、 Bellman-ford 算法、SPFA算法）

另一类是求图中每一对顶点间的最短路径,（floyed算法）

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
 2 #include
 3 #include
 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算法是所做的操作一样：

若存在边 ，使得：

则更新  值：

其实就是更新成较短的路径的长度呗，这就是三角变换

初始化的操作也是一样的：

现在我们将对边集合  中每条边都执行一次松弛视为一次迭代操作，现在我们来看迭代次数和图之间的关系（至于为啥要这样以后会说的）

那我们其实不难发现，在一个图中，有时只使用一次松弛操作就可以实现找到最优解，比如下面这张图：

我们如果按照：w(a,b) w(b,c) w(c d) 的顺序进行松弛：

对边  执行松弛函数，则 
对边  执行松弛函数，则 
对边  执行松弛函数，则 

那我们只要通过一次迭代操作就可以得到最优解了！

BUT！

如果我的运气很不好，（实际上是最坏），那一次就解决问题的概率其实不大，所以我至少要进行三次操作（由于过程太麻烦，这里就不过多赘叙）

那么发现规律：

最多要进行m（顶点数）-1 次操作，就能让所有的点确定，

即对于未确定的顶点，每次对边集进行一次操作，都至少会增加一个确定的点！

那现在我来推理一下：

 首先进行第一次迭代，那么b点一定会被确定，因为b只能从a点过去。

在第二次迭代的时候，由于我们确定了b点和a点，要不就是从a到b到c，要不就是直接从a到c 所以与a，b构成三角形的点c一定会被确定。

下面依次类推，都至少会确定一个点，证毕。

 

OK！现在我们就可以进入正题了——谜一样的  Bellman-Ford（转载，不喜勿喷）  

 

但是我们要有一点前提：

就是不能允许负权回路出现，因为如果有负权回路，那么这个最短路就会一直被更新（一直减减减），那就无法在 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可以让某些点在队里队外反复横跳（来回进出）

——————————————————手动分隔线————————————————————————