图的最小生成树---Prim算法

详解可以参照这里：最小生成树PRim算法理解

Prime算法的思想是枚举各个点能到达的所有的路，找出他们之间最短的，首先选择一个顶点加入生成树，然后找出一条边加入到生成树，重复n-1次，把所有的顶点都加入到生成树中，在这个算法里面也需要一个dis数组，不过它和迪杰斯特拉算法的不同之处在于，迪杰斯特拉的思想是dis[i]表示从1到i点的最小距离，而在Prime算法中，dis[i]代表每个项点到它离生成树最近的点的距离.然后通过类似松弛操作得出结果，时间复杂度为O(N^2)

给一组样例：

输入：

6 92 4 113 5 134 6 35 6 42 3 64 5 71 2 13 4 91 3 2输出：
19
代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <string>#include <iostream>#include <stack>#include <queue>#include <vector>#include <algorithm>#define mem(a,b) memset(a,b,sizeof(a))#define N 100+20#define M 100000+20#define MOD 1000000000+7#define inf 0x3f3f3f3fusing namespace std;int main(){    int n,m,min,t1,t2,t3;    int map[7][7],dis[7],vis[7]= {0};    int cnt=0,sum=0;    scanf("%d%d",&n,&m);    //初始化    for(int i=1; i<=n; i++)        for(int j=1; j<=n; j++)            if(i==j)                map[i][j]=0;            else                map[i][j]=inf;    //读入边    for(int i=1; i<=m; i++)    {        scanf("%d%d%d",&t1,&t2,&t3);        map[t1][t2]=t3;        map[t2][t1]=t3;    }    //初始化dis    for(int i=1; i<=n; i++)        dis[i]=map[1][i];    //Prime算法核心代码    vis[1]=1;    cnt++;    int k;    while(cnt<n)    {        min=inf;        for(int i=1; i<=n; i++)        {            if(!vis[i]&&dis[i]<min)            {                min=dis[i];                k=i;            }        }        vis[k]=1;        cnt++;        sum+=dis[k];        //扫描当前k的所有的边，以j为中间点，更新生成树到每一个非树顶点的距离        for(int j=1; j<=n; j++)        {            if(!vis[j]&&dis[j]>map[k][j])                dis[j]=map[k][j];//松弛，注意dis的含义        }    }    printf("%d",sum);    return 0;}