我用的是邻接矩阵保存的图

测试数据二所用的图如下：

具体说明都在下面这段代码里(如果不嫌弃可以仔细阅读)

#include
    
     #include
     
      #include
      
       #include
       
        #define inf 65535#include
        
         typedef struct Graph{    int vertex[100];    int arc[100][100];    int num_ver,num_edge;} Mygraph;void create(Mygraph *g)//建图{    int i,j,tmp,a,b,c;    scanf("%d%d",&g->num_ver,&g->num_edge);//输入结点数和边数    for(i=0; i
         
          num_ver; i++)//输入结点集 scanf("%d",&g->vertex[i]); for(i=0; i
          
           num_ver; i++)//边的权值初始化 { for(j=0; j
           
            num_ver; j++) g->arc[i][j]=inf; } for(i=0; i
            
             num_edge; i++)//输入边的权值 { scanf("%d%d%d",&a,&b,&c); g->arc[a][b]=c; g->arc[b][a]=c; }}void MiniSpanningTree(Mygraph *g){ int i,j,k,tmp,Min; int adjver[100]; //用来记录当前点是由哪个结点扩展而来，例如后面有一句printf("(%d,%d)\n",adjver[k],k); //说明k这个结点是由adjver[k]这个里存的结点扩展而来 int lowcost[100]; //用来存当前已经选择的点可以到达其他未选择的点的最短距离 lowcost[0]=0;//当lowcost[i]=0;说明i这个结点已经被选中 for(i=1; i
             
              num_ver; i++)//初始化lowcost数组 { lowcost[i]=g->arc[0][i]; //为什么是arc[0][i]呢？这是因为本例子选择从0这个结点开始找最小生成树 adjver[i]=0; //当前已经选择的点是0，到其他点只能从0开始(不管是否能到达，这些值后续会更新，不用担心从0这个点出发是否可以到达) } for(i=1; i
              
               num_ver; i++)//为什么从1开始？我的理解是已经选择了1个点(即是0这个点)，还要选择num_ver-1个点 { Min=inf;//Min用来找最小的边权值 j=1;//因为0这个点已经被选中，所以从1开始 //也就是说以后每一次循环均从lowcost[1]开始找最小边权值 while(j
               
                num_ver) { if(lowcost[j]!=0&&lowcost[j]
                
                 num_ver; j++) { //这段循环当时看了很久，其实就是用来更新lowcost[]这个数组，现在不是新选择了结点k吗，那么现在就需要 //更新加入k结点后到其他各未选节点的最短路径,同时更新加入k结点后还可以到达原来不能到达的点。举个例子， //若k=5，那么原来到达8这个结点的最短边是10，而现在发现5这个结点同样可以到达8，而且路径长度为6，那么现在就更新 //到达8这个结点最短边为6，adjver[8]=5(取得最短边，是从5出发的)；例如增加5这个结点后还可以到达原来不能到达的结点9， //那么更新到达9的最短边长 if(lowcost[j]!=0&&g->arc[k][j]
                 
                  arc[k][j]; adjver[j]=k; } } } }int main(){ int i,j,k,x,y,z; Mygraph G; printf("第一次测验\n"); create(&G); MiniSpanningTree(&G); printf("第二次测验\n"); create(&G); MiniSpanningTree(&G); return 0;}/*5 60 1 2 3 40 1 90 2 20 4 61 2 32 3 53 4 19 150 1 2 3 4 5 6 7 80 1 100 5 111 6 165 6 171 2 181 8 122 8 82 3 228 3 216 3 246 7 193 7 167 4 73 4 205 4 26*/