预习了一点图论的算法，记录一下：
我将分为三部分记录：
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算法是所做的操作一样：
若存在边 ，使得：
则更新 值：
其实就是更新成较短的路径的长度呗，这就是三角变换
初始化的操作也是一样的：
现在我们将对边集合 中每条边都执行一次松弛视为一次迭代操作，现在我们来看迭代次数和图之间的关系（至于为啥要这样以后会说的）
那我们其实不难发现，在一个图中，有时只使用一次松弛操作就可以实现找到最优解，比如下面这张图：
我们如果按照：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一定会被确定。
下面依次类推，都至少会确定一个点，证毕。
但是我们要有一点前提：
就是不能允许负权回路出现，因为如果有负权回路，那么这个最短路就会一直被更新（一直减减减），那就无法在 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++
④如果k=n-1,说明最小生成树已经生成，则break;
end;
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 }
代码那么那么详细，我就不解释了
就先记录到这吧，以后还会加一些题之类的，会日臻完善
拜拜！