贪心算法之prim算法

算法思路：
G=(V, E),首先置S＝{1},只要S是V的真子集，就进行如下的贪心选择，选取满足条件i属于S，j属于V－S，且
matrix[i][j]是最小的边，将j加入到S中，这个过程一直持续到S＝V为止，在这个过程中选择的所有边恰好构
成G的一棵最小生成树。

实现：对于每一个j属于V－S，closest[j]是j在S中的邻接点，它与j在S中的其它邻接点k相比有：
matrix[j][closest[j]] <= matrix[j][k],lowcost[j]的值就是matrix[j][closest[j]].

代码：

#include <stdio.h>
#include <string.h>

#define maxnodenum 100
#define maxedgenum 100
#define MAX_VALUE 100

int matrix[maxnodenum][maxnodenum];
int nodes[maxnodenum], lowcost[maxnodenum], closest[maxnodenum];
int nodenum, edgenum;
static void matrix_init(void);
static void prim(void);
static void print_mst(void);

int main(int argc ,char **argv)
{
        matrix_init();
        prim();
        print_mst();

        return 0;
}
static void matrix_init(void)
{
        int i, j, row, col, weight;

        printf("Input nodenum and edgenum:\n");
        scanf("%d %d", &nodenum, &edgenum);
        getchar();

        memset((void *)matrix, MAX_VALUE, sizeof(matrix));
        printf("Input all edges:\n");
        for(i = 1; i <= edgenum; i++){
                scanf("%d %d %d", &row, &col, &weight);
                getchar();
                matrix[row][col] = matrix[col][row] = weight;
        }
}

static void prim(void)
{
        int i, j, k, min;

        nodes[1] = 1;
        for(i = 2; i <= nodenum; i++){
                lowcost[i] = matrix[1][i];
                closest[i] = 1;
        }

        for(i = 1; i < nodenum; i++){
                min = MAX_VALUE;
                j = 1;
                for(k = 2; k <= nodenum; k++){
                        if(!nodes[k] && lowcost[k] < min){
                                min = lowcost[k];
                                j = k;
                        }
                }
                nodes[j] = 1;
                for(k = 2; k <= nodenum; k++){
                        if(!nodes[k] && matrix[j][k] < lowcost[k]){
                                lowcost[k] = matrix[j][k];
                                closest[k] = j;
                        }
                }
        }
}

static void print_mst(void)
{
        int i;

        printf("Print mst:\n");
        for(i = 2; i <= nodenum; i++){
                printf("%d %d %d\n", i, closest[i], lowcost[i]);
        }
}