图论用prim法求最小生成树

我用的是邻接矩阵保存的图
测试数据二所用的图如下：
具体说明都在下面这段代码里(如果不嫌弃可以仔细阅读)
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<cmath>
#define inf 65535
#include<algorithm>
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<g->num_ver; i++)//输入结点集
        scanf("%d",&g->vertex[i]);

    for(i=0; i<g->num_ver; i++)//边的权值初始化
    {
        for(j=0; j<g->num_ver; j++)
            g->arc[i][j]=inf;
    }
    for(i=0; i<g->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)
",adjver[k],k);
    //说明k这个结点是由adjver[k]这个里存的结点扩展而来
    int lowcost[100];
    //用来存当前已经选择的点可以到达其他未选择的点的最短距离
    lowcost[0]=0;//当lowcost[i]=0;说明i这个结点已经被选中
    for(i=1; i<g->num_ver; i++)//初始化lowcost数组
    {
        lowcost[i]=g->arc[0][i];
        //为什么是arc[0][i]呢？这是因为本例子选择从0这个结点开始找最小生成树
        adjver[i]=0;
        //当前已经选择的点是0，到其他点只能从0开始(不管是否能到达，这些值后续会更新，不用担心从0这个点出发是否可以到达)
    }
    for(i=1; i<g->num_ver; i++)//为什么从1开始？我的理解是已经选择了1个点(即是0这个点)，还要选择num_ver-1个点
    {
        Min=inf;//Min用来找最小的边权值
        j=1;//因为0这个点已经被选中，所以从1开始
        //也就是说以后每一次循环均从lowcost[1]开始找最小边权值
        while(j<g->num_ver)
        {
            if(lowcost[j]!=0&&lowcost[j]<Min)
            {
                Min=lowcost[j];
                k=j;
            }
            j++;
        }
         //现在k里存的是从当前以选择结点出发可以到达的最近的结点(即边权值最小)
        lowcost[k]=0;//选中k结点，讲lowcost[k]标记为0
        printf("(%d,%d)
",adjver[k],k);//打印新找到的边
        for(j=1; j<g->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]<lowcost[j])
            {
                lowcost[j]=g->arc[k][j];
                adjver[j]=k;
            }
        }
    }
    
}


int main()
{
    int i,j,k,x,y,z;
    Mygraph G;
      printf("第一次测验
");
    create(&G);
    MiniSpanningTree(&G);
    printf("第二次测验
");
    create(&G);
    MiniSpanningTree(&G);

    return 0;
}
/*
5 6
0 1 2 3 4
0 1 9
0 2 2
0 4 6
1 2 3
2 3 5
3 4 1

9 15
0 1 2 3 4 5 6 7 8
0 1 10
0 5 11
1 6 16
5 6 17
1 2 18
1 8 12
2 8 8
2 3 22
8 3 21
6 3 24
6 7 19
3 7 16
7 4 7
3 4 20
5 4 26
*/
图论 用prim法求最小生成树

图论用prim法求最小生成树
