本文共 1185 字，大约阅读时间需要 3 分钟。

【描述】：

采用邻接矩阵方式储存图，创建图，生成最小生成树。

【输入】：

7 9

【输出】：

0,5权值: 10 | 5,4权值: 25 | 4,3权值: 22 | 3,2权值: 12 | 2,1权值: 16 | 1,6权值: 14 | 

/*7 90 1 2 3 4 5 60 1 280 5 101 2 161 6 142 3 123 4 223 6 184 5 254 6 24*/#include
   
    using namespace std;/*宏定义*/#define INFINITY 65535#define MAX_NUM 100#define EleType int#define EdgeType int/*图的结构体*/typedef struct {    EleType vertex[MAX_NUM];    //顶点表    EdgeType arc[MAX_NUM][MAX_NUM];  //邻接矩阵    int VertexNum;  //顶点数    int ArcNum; //边数}GraphType,*GraphPointer;//声明图GraphType graph;/*邻接矩阵的创建*/void CreateGraph(){    int w;  //权值    int n,k;    //输入顶点数和边数    cin>>graph.VertexNum>>graph.ArcNum;    //输入所有顶点    for(int i = 0; i
    
     >graph.vertex[i];    }    //初始化邻接矩阵    for(int j = 0; j
     
      >n>>k>>w;        graph.arc[n][k] = w;        //无向图邻接矩阵对称原则        graph.arc[k][n] = w;    }    }/*prim*/void prim(){    int n,min;  //n是当前最小值的下标（根据lowcost数组得出 ）    int adjver[MAX_NUM];    //所有vertex 与 已经加入到MST中，可以和其组成min距离的顶点相连    int lowcost[MAX_NUM];   //所有vertex 与 MST的最小距离（权值）    adjver[0] = 0;  //相连    lowcost[0] = 0; //更新权值    //将第一顶点v0加入到MST中的第一轮更新    for(int i = 1; i