/*

 普里姆算法的主要思想：

     利用二维数组把权值放入，然后找在当前顶点的最小权值，然后走过的路用一个数组来记录

 */

 # include <stdio.h>

 typedef char VertexType;//定义顶点类型

 typedef int EdgeType;//定义边上的权值类型

 # define MAX_VERTEX //最大顶点个数

 # define INFINITY //用65535代表无穷大

 typedef struct

 {//邻接矩阵存储结构

     VertexType vexs[MAX_VERTEX];//顶点表

     EdgeType arc[MAX_VERTEX][MAX_VERTEX];//邻接矩阵

     int numVertexs, numEdges;//图中当前的顶点数和边数

 }MGraph;

 void CreateMGraph(MGraph *G)

 {

     int i, j;

     G->numEdges=;

     G->numVertexs=;

     for (i = ; i < G->numVertexs; i++)

     {

         for ( j = ; j < G->numVertexs; j++)

         {

             if (i==j)

                 G->arc[i][j]=;

             else

                 G->arc[i][j] = G->arc[j][i] = INFINITY;

         }

     }

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=;

     G->arc[][]=; 

     for(i = ; i < G->numVertexs; i++)

     {

         for(j = i; j < G->numVertexs; j++)

         {

             G->arc[j][i] =G->arc[i][j];

         }

     }

 }

 void MinSpanTree_Peim (MGraph &G)

 {//普里姆算法，最小生成树

     int min, i, j, k;

     int add=;

     int adjvex[MAX_VERTEX];

     int lowcost[MAX_VERTEX];

     lowcost[] = ;

     adjvex[] = ;

     for (i=; i<G.numVertexs; i++)

     {//若是从v0顶点开始查找，从顶点v0的矩阵全部赋值到lowcost数组中，adjvex数组全部为0；

         lowcost[i] = G.arc[][i];//二维数组存放的权值

         adjvex[i] = ;//所有都为0

     }

     for (i=; i<G.numVertexs; i++)

     {//最小生成树

         min = INFINITY;//无穷大

         j=;

         k=;

         while (j < G.numVertexs)

         {//查找lowcost数组中最小的值，把最小的值赋给min，且最小值的下表赋给k

             if (lowcost[j]!= && lowcost[j]<min)

             {

                 min = lowcost[j];//存放最小的权值

                 k = j;//把存放最小权值的顶点下标

             }

             j++;

         }

         printf ("(%d——%d)\n", adjvex[k], k);

         add = add + G.arc[adjvex[k]][k];

         /*因为52~56行已经把adjvex数组全部赋值为0，所以一开始打印出来的就是0，后来打印出来的就是以上一个在lowcost

         数组中最小值的下表(下表对应的顶点)，顶点的矩阵中比当前lowcost数组中的值还要小的值的下标，和lowcost数组中最小值的下标*/

         lowcost[k] = ;

         //若刚才存放最小权值的顶点是1(k=1),则下面就for循环就从发1的二位数组继续寻找最小生成树

         for (j=; j<G.numVertexs; j++)

         {//以在lowcost数组中最小值的下表作为二位数组的第一个下标与当前lowcos数组中的值进行比较。

          //查找最小值

             if (lowcost[j]!= && G.arc[k][j]<lowcost[j])//t

             {

                 lowcost[j] = G.arc[k][j];//

                 adjvex[j] = k;

             }

         }

     }

     printf ("%d\n", add);

     return;

 }

 int main (void)

 {

     MGraph G;

     CreateMGraph (&G);

     MinSpanTree_Peim (G);

     return ;

 }

 /*

                                         在vc++6.0运行结果：

 请输入顶点数和边数：9 15

 请输入第1个顶点信息：v0

 请输入第2个顶点信息：v1

 请输入第3个顶点信息：v2

 请输入第4个顶点信息：v3

 请输入第5个顶点信息：v4

 请输入第6个顶点信息：v5

 请输入第7个顶点信息：v6

 请输入第8个顶点信息：v7

 请输入第9个顶点信息：v8

 请输入边(vi,vj)上的下表i，下表j和权w：0 1 10

 请输入边(vi,vj)上的下表i，下表j和权w：0 5 11

 请输入边(vi,vj)上的下表i，下表j和权w：1 6 16

 请输入边(vi,vj)上的下表i，下表j和权w：1 2 18

 请输入边(vi,vj)上的下表i，下表j和权w：1 8 12

 请输入边(vi,vj)上的下表i，下表j和权w：2 8 8

 请输入边(vi,vj)上的下表i，下表j和权w：2 3 22

 请输入边(vi,vj)上的下表i，下表j和权w：8 3 21

 请输入边(vi,vj)上的下表i，下表j和权w：6 5 17

 请输入边(vi,vj)上的下表i，下表j和权w：6 3 24

 请输入边(vi,vj)上的下表i，下表j和权w：6 7 19

 请输入边(vi,vj)上的下表i，下表j和权w：3 4 20

 请输入边(vi,vj)上的下表i，下表j和权w：3 7 16

 请输入边(vi,vj)上的下表i，下表j和权w：4 7 7

 请输入边(vi,vj)上的下表i，下表j和权w：4 5 26

 (0——1)

 (0——5)

 (1——8)

 (8——2)

 (1——6)

 (6——7)

 (7——4)

 (7——3)

 Press any key to continue

 */