关于图论算法
预习了一点图论的算法，记录一下：
我将分为三部分记录：
1.概念&一笔画问题
2.最短路算法
3.最小生成树算法
1st. 一笔画问题
首先明确以下几个概念：
1、欧拉通路：恰好通过图中的每条边仅一次的通路。
2、欧拉回路：是欧拉路径且起点和终点是同一个点。
3、欧拉图：存在欧拉回路的图。
关于一笔画问题的定理：
存在欧拉路的条件：图是连通的，且存在0个或2个奇点。 如果存在2个奇点，那么这两个奇点一定是这个图的起点和终点。
如果存在欧拉回路的话，就不会有奇点。
其实我们要探究的一笔画问题就是探究是否存在欧拉回路
——“问题来了，怎样求得欧拉路径呢？”
——“用DFS！”
首先确定起点和终点，也就是输入再存储这张图，记录每个点的度。然后找有没有奇点，如果有的话，就将其当成起点或终点。如果没有，就可以从任何一个点开始。
#include<iostream>
#define N 1001
using namespace std;
int g[N][N];//存图
int du[N];//记录每个点的度
int lu[N];//记录最后要输出的点的顺序
int n,cnt,e;
void dfs_lu(int i)
{
for(int j=1;j<=n;j++)
if(g[i][j]==1)
{
g[i][j]=0;
g[j][i]=0;
dfs_lu(j);
}
lu[cnt++]=i;
}
int main()
{
cin>>n>>e;
int x,y;
for(int i=1;i<=e;i++)
{
cin>>x>>y;
g[x][y]=1;
g[y][x]=1;
du[x]++;
du[y]++;
}
int start=5;//如果没有环（即没有奇点）就直接从1开始，当然从任何一个点开始都是可以的！！！
for(int i=1;i<=n;i++)
{
if(du[i]%2==1)
start=i;//记录起点
break;
}
cnt=0;
dfs_lu(start);
for(int i=0;i<cnt;i++)
{
cout<<lu[i]<<" ";
}
return 0;
} 有欧拉图，就还会有哈密顿图：
定义：
哈密尔顿通路：通过图中每个顶点仅一次的通路。
哈密尔顿回路：通过图中每个顶点仅一次的回路。
哈密尔顿图：存在哈密尔顿回路的图。
其实哈密顿图和欧拉图的区别就是一个是经过所有的边，一个是经过所有的点
其实不准确，因为只要经过所有的边，就一定会经过所有的点，但是经过所有的点不一定经过所有的边，所以他们的区别实际上是：
一个是要经过所有的点且经过所有的边，一个是经过所有的点但不用非要经过所有的边
——————————————————手动分隔线————————————————————————
2nd. 最短路问题
有四种方法，分别是：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两点之间路径长度的最小
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int d[101][101];
int main()
{
int n,m,p,q;
cin>>n>>m>>p>>q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
d[i][j]=1001;
}
}
//初始化将每条边变成一个很大的数
for(int i=1;i<=n;i++)
{
d[i][i]=0;
}
//自己到自己的长度是0
int i,j,len;
for(int ha=1;ha<=m;ha++)
{
cin>>i>>j>>len;
d[i][j]=len;
d[j][i]=len;
}//输入边的长度
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(d[i][k]+d[k][j]<d[i][j])
{
d[i][j]=d[i][k]+d[k][j];
}
}
}
}
//寻找最短距离
cout<<d[p][q];
return 0;
} 
