Prim算法（邻接矩阵无相图）求最小生成树 C 实现 ~

核心思想：贪心

算法过程：

1).输入：一个加权连通图，其中顶点集合为V，边集合为E； 2).初始化：V_new = {x}，其中x为集合V中的任一节点（起始点），E_new = {},为空； 3).重复下列操作，直到V_new = V： a.在集合E中选取权值最小的边<u, v>，其中u为集合V_new中的元素，而v不在V_new集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； b.将v加入集合V_new中，将<u, v>边加入集合E_new中； 4).输出：使用集合V_new和E_new来描述所得到的最小生成树。

核心算法:

void Prim(Graph g, int start)  
{  
int sum = 0;
int index = 0;
int i, j;
char prims[MAXVEX];
prims[index++] = g.vex[start];

for(i = 0; i < g.vex_num; i++ ){
dist[i] = g.edge[start][i];
}
dist[start] = 0; //需要 
int min, u, v;
int pre;
for(i = 0; i < g.vex_num; i++ ){
if(start == i)
continue;
min = INFINITY;
for(j = 0; j < g.vex_num; j++ ){
if(dist[j] != 0 && dist[j] < min){
min = dist[j];
u = j;
}  
}
if(dist[u] != 0)// not really needed anymore. 
prims[index++] = g.vex[u];
dist[u]= 0;
for(v = 0; v < g.vex_num; v++ ){
if(dist[v] != 0 && g.edge[u][v] < dist[v])
dist[v] = g.edge[u][v];
}
}
for(i = 1; i < g.vex_num; i++){
min = INFINITY;//可以排除u v两点不存在边的情况 
v = get_pos(g, prims[i]);
for(j = 0; j < i; j++ ){
u = get_pos(g, prims[j]);
if(g.edge[u][v] < min){
min = g.edge[u][v];
}
}
sum += min;
}

printf("prim %c = %d\n",g.vex[start],sum);
for(i = 0; i < index; i++ ){
printf("%c",prims[i]);
}
}  

完整实现：

#include<stdio.h>    
#include<stdlib.h>    
#include<ctype.h>   
#define NOTEXIST -1  
#define BEGIN -1   
#define MAXVEX 100    
#define INFINITY 65535    
#define TRUE 1    
#define FALSE 0     
typedef int EdgeType;  
typedef char VertexType;    
int dist[MAXVEX];  //dist指 从 该点到被收录的各点中 距离的最小值 
typedef struct Graph {  
    VertexType vex[MAXVEX];  
    EdgeType edge[MAXVEX][MAXVEX];  
    int vex_num, edge_num;  
}Graph;  

char read_char()  
{  
    char ch;  
    do {  
        ch = getchar();  
    } while (!isalpha(ch));  
    return ch;  
}  

int get_pos(Graph g, char ch)  
{  
    int i;  
    for (i = 0; i < g.vex_num; i++) {  
        if (g.vex[i] == ch)  
            return i;  
    }  
    return -1;  
}  

void create_graph(Graph *g)  
{  
    int i, j, k;  
    printf("请输入顶点数与边数:\n");    
    scanf("%d%d", &g->vex_num, &g->edge_num);  
    for (i = 0; i < g->vex_num; i++) {  
        for (j = 0; j < g->vex_num; j++) {  
            if (i == j) {  
                g->edge[i][j] = 0;  
            }  
            else  
                g->edge[i][j] = INFINITY;  
        }  
    }  
    printf("请输入顶点信息:\n");    
    for (i = 0; i < g->vex_num; i++) {    
        g->vex[i] = read_char();  
    }  
    printf("请输入边的信息:\n");    
    char c1, c2;  
    int p1, p2, w;  
    for (k = 0; k < g->edge_num; k++) {  
        c1 = read_char();  
        c2 = read_char();  
        scanf("%d", &w);  
        p1 = get_pos(*g, c1);  
        p2 = get_pos(*g, c2);  
        g->edge[p1][p2] = w;//有向边的权重   
g->edge[p2][p1] = w; 
    }  
}  

void Prim(Graph g, int start)  
{  
int sum = 0;
int index = 0;
int i, j;
char prims[MAXVEX];
prims[index++] = g.vex[start];

for(i = 0; i < g.vex_num; i++ ){
dist[i] = g.edge[start][i];
}
dist[start] = 0; //需要 
int min, u, v;
int pre;
for(i = 0; i < g.vex_num; i++ ){
if(start == i)
continue;
min = INFINITY;
for(j = 0; j < g.vex_num; j++ ){
if(dist[j] != 0 && dist[j] < min){
min = dist[j];
u = j;
}  
}
if(dist[u] != 0)// not really needed anymore. 
prims[index++] = g.vex[u];
dist[u]= 0;
for(v = 0; v < g.vex_num; v++ ){
if(dist[v] != 0 && g.edge[u][v] < dist[v])
dist[v] = g.edge[u][v];
}
}
for(i = 1; i < g.vex_num; i++){
min = INFINITY;//可以排除u v两点不存在边的情况 
v = get_pos(g, prims[i]);
for(j = 0; j < i; j++ ){
u = get_pos(g, prims[j]);
if(g.edge[u][v] < min){
min = g.edge[u][v];
}
}
sum += min;
}

printf("prim %c = %d\n",g.vex[start],sum);
for(i = 0; i < index; i++ ){
printf("%c ",prims[i]);
}
}  

void print_graph(Graph g)  
{  
    int i, j;  
    for (i = 0; i < g.vex_num; i++) {  
        for (j = 0; j < g.vex_num; j++) {  
            if (g.edge[i][j] == INFINITY)  
                printf("%5c", '*');  
            else {  
                printf("%5d", g.edge[i][j]);  
            }  
        }  
        printf("\n");  
    }  
}   

int main()  
{  
    Graph g;  
    int start, end;  
    char c1;
    create_graph(&g);  
    printf("请输入起始点:\n");  
    c1 = read_char(); 
    start = get_pos(g, c1);         
    Prim(g, start);  
    getchar();  
    return 0;  
}