Prim 最小生成树

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 1000
#define INF 0x3f3f3f3f

using namespace std;

int map[MAX][MAX];
int vis[MAX];        //是否被访问过 
int dis[MAX];        //该集合到所有点的最短距离       
int n,m;

void prim(){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    int min_,k;
    for(int i=1;i<=n;i++){        //依次加入每一个顶点
        min_=INF;
        k=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j] && dis[j]<min_){            //找当前不在集合V‘内且与集合V‘最近的一个点
                min_=dis[j];
                k=j;
            }
        }
        if(k==-1)    return ;        //图不连通 
        vis[k]=1;for(int j=1;j<=n;j++){            //更新与k点相邻的点v到集合V‘的最短距离
            if(!vis[j]){   
                if(dis[j]>map[k][j]){          //点v没有被访问过且点v到点k的距离小于点v到集合V‘的距离
                    dis[j]=map[k][j];
                }
            }
        }
    }
}