#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define maxSize 5
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
struct VType{//顶点的值 int no;
};
struct MGraph{//邻接矩阵 int edges[maxSize][maxSize];int n,e;//存放顶点信息 VType* vtype[maxSize];
};
void printArr(int a[maxSize][maxSize]){for(int i = 0;i < maxSize;++i){for(int j = 0;j < maxSize;++j){printf("%-3d",a[i][j]);}printf("\n");}
}
//创建邻接矩阵
void create(MGraph *&g,int n){//1.初始化结构体g = (MGraph*)malloc(sizeof(MGraph));g->e = 0;g->n = n;int i;//2.while循环,循环创建各个VType结点,并且为顶点的值赋值 while(i < maxSize){VType* v = (VType*)malloc(sizeof(VType));v->no = i;g->vtype[i++] = v;}for(int i = 0;i < maxSize; ++i){//这里创建的是无向图,所以是j=i,减少输入 for(int j = i;j < maxSize;++j){int weight;//1.用户输入权值//2.给用户显示当前输入的是那个到那个的权值//3.如果用户输入了权值为 无穷 则两个结点不相连,无穷使用了 #include <limits.h>这个库的INT_MAX if(i!=j){printf("Please input node %d ---> node %d weight\n",i,j);printf("If input -1 represent no road from node %d to node %d\n",j,i);printf("weight( %d -> %d ):",i,j);scanf("%d",&weight); if(weight != -1){g->e++;}else{weight = INT_MAX;}}else{weight = 0;}g->edges[i][j] = weight;g->edges[j][i] = weight; }} //输出一下看一下
// printArr(g->edges);
}
//普利姆最小生成树算法
void prim(MGraph *g,int v0,int &sum){//到树的最小花费数组 int lowcost[maxSize];//节点访问与否数组 int vext[maxSize];//刚刚进树的结点 int v;//看成树 v=v0;//树只有一个根节点,其权值为0 sum = 0; //首次更新各结点到树的最小权值 for(int i = 0;i < maxSize; ++i){lowcost[i] = g->edges[v][i];vext[i] = 0; }//标记结点已经访问vext[v] = 1;//对其余的n-1个结点进行遍历 for(int i = 0;i < maxSize-1; i++){//最小值开始取一个极大数 int min = INT_MAX;//从lowcost数组中的出目前到树最小的结点,如果这个结点已经被访问了即已经被划进树中就不算了//负责存储最小值的下标 int k;for(int j = 0;j < maxSize; ++j){if(vext[j] == 0 && lowcost[j] < min){min = lowcost[j];k = j;}}vext[k] = 1;v = k;sum += min;//更新各结点到树的最小权值 for(int i = 0;i < maxSize;i++){//如果有某个结点的权值到树的权值更小了,就改变lowcost if(lowcost[i] > g->edges[v][i]){lowcost[i] = g->edges[v][i]; }}}
}
int main(int argc, char** argv) {MGraph *g;create(g,maxSize);int sum = 0;prim(g,2,sum);printf("%d",sum);return 0;
}