最小生成树-prim算法

参考资料：
http://blog.csdn.net/yeruby/article/details/38615045
prim算法不太好理解，在这里记录一下：

2个数组的解释

adjvex[i]:表示对应lowcost[i]的起点
lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0
如：adjex[2] = 1，lowcast[2] = 6; 表示 顶点 1 到顶点2 的距离 是 6；

C语言实现代码（无向矩阵）：

#include <stdio.h>
#include <stdlib.h>

#define MAX_LENGTH 100
#define INFINITY 65536  // 表示无边连接
#define NO %;


typedef struct Grapha{
    char vertext[MAX_LENGTH];
    int arc[MAX_LENGTH][MAX_LENGTH]; // 邻接矩阵
    int numVertexts, numEdges;  // 顶点数与边数
} Grapha, *P_Grapha;

// 创建顶点方法， 9个顶点，8条边
void createVertex(P_Grapha G) {
    G->numVertexts = 9;
    
    G->vertext[0] = 'A';
    G->vertext[1] = 'B';
    G->vertext[2] = 'C';
    G->vertext[3] = 'D';
    G->vertext[4] = 'E';
    G->vertext[5] = 'F';
    G->vertext[6] = 'G';
    G->vertext[7] = 'H';
    G->vertext[8] = 'I';
}

// 8 条带权的边，理解成双向
void createEdges(P_Grapha G) {
    G->numEdges = 8;
    
    int i, j;
    
    // 初始化边（无向）
    for(i=0; i<G->numVertexts; i++) {
        for(j=0; j<G->numVertexts; j++) {
            if(i == j) {
                G->arc[i][j] = 0;
            } else {
                G->arc[i][j] = INFINITY;
            }
        }
    }
    
    // 设置权值
    
    G->arc[0][1] = 10;
    G->arc[0][5] = 11;
    
    G->arc[1][0] = 10;
    G->arc[1][2] = 18;
    G->arc[1][6] = 16;
    G->arc[1][8] = 12;
    
    G->arc[2][1] = 18;
    G->arc[2][3] = 22;
    G->arc[2][8] = 8;
    
    G->arc[3][2] = 22;
    G->arc[3][4] = 20;
    G->arc[3][7] = 16;
    G->arc[3][8] = 21;
    
    G->arc[4][3] = 20;
    G->arc[4][5] = 26;
    G->arc[4][7] = 7;
    
    G->arc[5][0] = 11;
    G->arc[5][4] = 26;
    G->arc[5][6] = 17;
    
    G->arc[6][1] = 16;
    G->arc[6][5] = 17;
    G->arc[6][7] = 19;
    
    G->arc[7][3] = 16;
    G->arc[7][4] = 7;
    G->arc[7][6] = 19;
    
    G->arc[8][1] = 12;
    G->arc[8][2] = 8;
    G->arc[8][3] = 21;
}


void createMGrah(P_Grapha *G) {

    (*G) = (P_Grapha)malloc(sizeof(Grapha));
    createVertex(*G);
    createEdges(*G);
    
    int i, j;
    // 输出矩阵
    printf("------------ 无向邻接矩阵 ----------\n");
    for(i=0; i<(*G)->numVertexts; i++) {
        if(i == 0) {
            printf("----%2d |",i);
        } else {
            printf("%2d |",i);
        }
    }
    printf("\n");
    
    for(i=0; i<(*G)->numVertexts; i++) {
        if(i == 0) {
            printf("----%2c |",(*G)->vertext[i]);
        } else {
            printf("%2c |",(*G)->vertext[i]);
        }
    }
    printf("\n");
    
    // 实际矩阵
    for(i=0; i<(*G)->numVertexts; i++) {
        for(j=0; j<(*G)->numVertexts; j++) {
            if(j == 0) {
                if((*G)->arc[i][j] == INFINITY) {
                    printf("%2d-%c|%2c|",i,(*G)->vertext[i], '%');
                } else {
                    printf("%2d-%c|%2d|",i,(*G)->vertext[i], (*G)->arc[i][j]);
                }
            } else {
                if((*G)->arc[i][j] == INFINITY) {
                   printf("%2c |",'%');
                } else {
                    printf("%2d |",(*G)->arc[i][j]);
                }
            }
        }
        printf("\n");   // 换行
    }
}

// 最小生成树
// 例如adjvex[3] = 5  lowcost[3] = 8即表示序号为5的顶点（即第6个顶点）到序号为3（两个数组的下标都为3 即第4个顶点）的顶点的边的权值为8
void miniSpanTree_Prim(Grapha G) {
    printf("=============== 最小生成树 ============\n");   // 换行
    
    int min, i, j, k;
    int adjvex[MAX_LENGTH];     // 保存相关顶点下标
    int lowcost[MAX_LENGTH];    // 保存相关顶点间边的权值
    
    lowcost[0] = 0;     // V0作为最小生成树的根开始遍历，权值为0，即V0加入生成树
    adjvex[0] = 0;      // 初始化第一个顶点下标为0
    
    // 初始化操作
    for(i = 1; i<G.numVertexts; i++) {
        lowcost[i] = G.arc[0][i];   // 将邻接矩阵第0行所有权值先加入数组
        adjvex[i] = 0;              // 将V0顶点与之有边的权值存入数组 并初始化都为V0的下标；
    }
    
    // 真正构建最小生成树的过程
    for(i=1; i<G.numVertexts; i++) {
        min = INFINITY;
        j = 1;
        k = 0;
        
        // 遍历全部顶点，找到最小的权值 (第一次循环时，找出第0行最小的权下标)
        while(j<G.numVertexts){
            // 找出 lowcost数组已存储最小权值
            if(lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;      // 将发现的最小权值的下标存入k，以待使用。
            }
            j++;
        }
        
        // 打印当前顶点边中权值最小的边
        printf("(%d,%d)", adjvex[k], k);  // 输出当前顶点边中权值最小的边，adjvex[k] 为上一个顶点
        lowcost[k] = 0;                   // 将当前顶点的权值设置为0，表示此顶点已经完成任务
        if(i == G.numVertexts - 1) {
            lowcost[k] = 0;
        }
        
        // 邻接矩阵k行逐个遍历全部顶点，找最小权值
        for( j=1; j < G.numVertexts; j++ ) {
            if( lowcost[j]!=0 && G.arc[k][j] < lowcost[j] ) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;  // 记住相关的顶点
            }
        }
    }
}


int main(int argc, const char * argv[]) {
    // 创建图
    P_Grapha G;
    createMGrah(&G);
    miniSpanTree_Prim(*G);
    return 0;
}