本文共 4255 字，大约阅读时间需要 14 分钟。
核心思想：贪心
算法过程：
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#include #include #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; }
转载地址：http://iximi.baihongyu.com/