1.求最小生成树有两种方法：
①克鲁斯卡尔算法：这个算法是以边为单位（包括边的所有的信息：两个端点+权值）进行存储的，然后将边按照权值的从小到大的顺序进行排序，然后将第一条边连接起来，第二条边连接起来，就这样一直循环，直到所有的边都被连接起来为止，在这期间，你需要判断那两个点是否已经连接过了，如果连接过了，就不需要连接了（连接过的意思是：只要从一个端点能间接地到达另一个端点就算是连接过），如果没有连接过，就将其连接上！因为这是按照权值从小到达的顺序连接的，所以先连接的权值肯定小，最终求出来一定是最小生成树！（主要以并查集为工具）细节：1.克鲁斯卡尔算法是用结构体来存储边的信息的！而普里母算法是用邻接矩阵来存储边的信息的！2.克鲁斯卡尔是以边为单位进行增边，而普里母是以点为单位进行增边！
代码实现：
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int pre[110];
struct node
{
int u,v,w;
}p[10000];
int cmp(node a,node b)
{
return a.w<b.w;
}
void init()
{
for(int i=1;i<=m;i++)
pre[i]=i;
}
int find(int x)
{
int r=x;
while(r!=pre[r])
{
r=pre[r];
}
int i,j;
i=x;
while(i!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
int join(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
pre[fx]=fy;
return 1;
}
return 0;
}
int main()
{
int sum,t;
while(scanf("%d%d",&n,&m)&&n)
{
sum=0;t=0;
init();
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
}
sort(p,p+n,cmp);
for(int i=0;i<n;i++)
{
if(join(p[i].u,p[i].v))
{
sum+=p[i].w;
}
}
printf("%d\n",sum);
}
return 0;
}
②普里母算法：这个算法是通过邻接矩阵来存储边的信息的（第一个下标代表左端点，第二个下标代表右端点，存储的值代表这条边对应的权值），然后首先以某一个点为起点（一般以1为起点），先将这个点加进集合里面，然后将其他的点到这个集合的距离赋值给dis数组（dis数组用来保存所有的点到集合的距离的最小的值，进集合的点的dis值为这个点与集合里面的其他的点的最短的距离，也就是这个最小生成树的一个枝条的长度），然后通过循环找集合外面的点到集合里面的点的最小值，然后保存下标将其放进集合里面（也就是vis[k]=1）,然后更新其他的点到集合的点（也就是对比之前的最短的距离与到新近的这个点的距离进行比较，找最小的距离保存到dis数组里面！），然后重新找集合外面的点到集合的距离的最小值的点，将其放进集合，然后继续更新最小的距离，直到所有的点都放进集合为止（也就是让循环n-1次停止循环）！
代码实现：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int n,m;
int d[105][105];
int dis[105];
int vis[105];
void init()
{
int a,b,c;
memset(vis,0,sizeof(vis));
memset(d,INF,sizeof(d));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
d[a][b]=d[b][a]=c;
}
vis[1]=1;
for(int i=1;i<=n;i++)
{
dis[i]=d[1][i];
}
dis[1]=0;//这个1号点一定要初始化为0，因为刚开始赋值为INF，然后直接放进集合内，所以他到集合的距离为0！
}//这一点必须记住！
void prim()
{
int min,k,t=0;
for(int i=1;i<n;i++)
{
min=INF;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&(dis[j]<min))
{
min=dis[j];
k=j;
}
}
if(min==INF)//当所有的点到集合的距离都为INF，则说明这个点与集合之间没有路，直接跳出，输出？
{
break;
}
vis[k]=1;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&(dis[j]>d[k][j]))
{
dis[j]=d[k][j];
}
}
}
int sum=0;
for(int i=1;i<=n;i++)
sum+=dis[i];
printf("%d\n",sum);
}
int main()
{
while(scanf("%d%d",&m,&n)&&m)
{
init();
prim();
}
return 0;
}
2.求最短路径的三种方法：
①迪杰斯特拉算法：（这个也是用邻接矩阵保存边的长度，以点为单位进行更新）这个算法的思想与求最小生成树的算法的思想几乎一样，就是这个在求最短路径的时候将起点固定了所以你必须是以给定的点为起点，然后在更新的时候，你不是将到集合的距离更新，而是将到起点的距离进行更新，但是因为你的dis数组中保存的是到起点的距离，所以你只需要将每次的dis数组里面的值与进集合里面的点的dis值加上进集合里面的点与外面的点之间的距离进行比较，然后取较小的值，就是我们更新的值，每次都将dis的值的最小的值放进集合取更新其他的值，就这样循环n-1次直到将所有的点都放进集合为止！用这种方法计算最终dis里面的值是所有的点到起点的距离！
【不适用计算有负权边的图，时间复杂度低】
注意：
1.有重边的要特殊处理（map[i][j]>c;map[i][j]=c）;
2.map初始化时要记i==j时map[i][j]=0;否则map[i][j]=INF;
模板：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int d[205][205];
int dis[205];
int vis[205];
int n,m,x,y;
void init()
{
int a,b,c;
memset(d,INF,sizeof(d));
memset(vis,0,sizeof(vis));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(d[a][b]>c)//这一点一定要注意！万一遇到多条a到b的路的话，要取较小的值！
{
d[a][b]=d[b][a]=c;
}
}
scanf("%d%d",&x,&y);
for(int i=0;i<n;i++)
{
dis[i]=d[x][i];
}
dis[x]=0;
vis[x]=1;
}
void dijkstra()
{
int min,k;
for(int i=0;i<n;i++)
{
min=INF;
for(int j=0;j<n;j++)
{
if(!vis[j]&&dis[j]<min)
{
min=dis[j];
k=j;
}
}
if(min==INF)
break;
vis[k]=1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&dis[j]>dis[k]+d[k][j])
{
dis[j]=dis[k]+d[k][j];
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
dijkstra();
if(dis[y]==INF)
printf("-1\n");
else
printf("%d\n",dis[y]);
}
return 0;
}
②SPFA算法：（建立邻接表，以点为单位进行加边）首先是给定起点，将起点放进队列，然后起点出队列，然后在起点的周围找与起点相连的点,放进队列里面（因为刚开始的时候除了起点的dis值外其他的点的dis值都是INF，所以肯定每个与起点相连的点到起点的值一定大于起点的dis值加上他们之间的边长），然后再将进队列的点出队列然后在他们周围找经过它们距离起点的距离比不经过它们距离起点的距离看看哪个大，如果经过它们的距离小，则将最小的距离进行更新，并且将与它们相连的点放进队列，然后继续出队列更新与它们相连的点，直至所有的点都出队列为止！（也就是进队列的点的周围的点都满足到原点的距离是最小的了，然后就没有点再进队列了，只有出队列的点，最终进队列的点都出来了，所有的点的dis值也就是到原点的最小的距离了！）
【能够计算有负权边的图，时间复杂度不确定，能够判断是否有负环】
代码（模板）：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f//这里面不能用0xfffffff，因为用这个不能用memset来赋值！
using namespace std;
int n,m;
struct Edge
{
int from, to, val, next;
}edge[10005];
int edgenum;
int dis[105];
int vis[105];
int head[10005];
void init()
{
edgenum=0;
memset(head,-1,sizeof(head));
}
void addEdge(int u,int v,int w)//建立邻接表！
{
Edge E={u,v,w,head[u]};//u为起点，v为终点，w为权值，head为同起点的上一条边的编号
edge[edgenum]=E;
head[u]=edgenum++;
}
void getmap()
{
int a,b,c;
for(int i=0;i<m;i++)//以一个点为起点建立邻接表！
{
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
addEdge(b,a,c);
}
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));
}
void SPFA()
{
queue<int>q;
q.push(1);
dis[1]=0;
vis[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)//邻接表！（以一个点为中心来遍历相邻的点！）
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)//更新
{
dis[v]=dis[u]+edge[i].val;
if(vis[v]==0)
{
vis[v]=1;//赋值号！
q.push(v);//因为有可能更新的值对其他的点的最短的距离会造成影响，所以要将其放进队列，然后以这个点为起点再将其他的点的最短距离进行更新！
}
}
}
}
printf("%d\n",dis[n]);
}
int main()
{
while(scanf("%d%d",&n,&m)&&(n||m))
{
init();
getmap();
SPFA();
}
}
③弗洛伊德算法：是dp算法的一种，它是利用其他的点作为断点来更新任意两点之间的距离，最终求的就是任意两点之间的距离，边的权值可正可负，但是时间复杂度较高，只能处理数据量将少的题，一般最好不用！
优缺点：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int n,m;
int map[205][205];
int x,y;
void init()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)
{
map[i][j]=0;
}
else
{
map[i][j]=INF;
}
}
}
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]>c)
{
map[a][b]=map[b][a]=c;
}
}
scanf("%d%d",&x,&y);
}
void floyd()
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
floyd();
if(map[x][y]==INF)
printf("-1\n");
else
printf("%d\n",map[x][y]);
}
return 0;
}