题目简述：假如有一个无向连通图，有n个顶点，有许多（带有权值即长度）边，让你用在其中选n-1条边把这n个顶点连起来，不漏掉任何一个点，然后这n-1条边的权值总和最小，就是最小生成树了，注意，不可绕成圈。
思路简介：对比普里姆和克鲁斯卡尔算法，克鲁斯卡尔算法主要针对边来展开，边数少时效率比较高，所以对于稀疏图有较大的优势；而普里姆算法对于稠密图，即边数非常多的情况下更好一些。其思路为将边按照权值从小到大排列，先取出最小的边，，再取出第二小的边，直到连接所有顶点，其中要注意不能将同一条边连接在同一颗树上，故而每一步都要设立一个树的终点，如果终点为同一个，则应当换下一条边。
简单代码：
#include <iostream> #include <cmath> #include <stdio.h> #include <cstdio> #include <cstring> #include<algorithm> #include<time.h> #include<math.h> #include <stdlib.h> #include <string.h> using namespace std; #define MAX 100 // 矩阵最大容量 #define INF (~(0x1<<31)) // 最大值(即0X7FFFFFFF) #define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z'))) #define LENGTH(a) (sizeof(a)/sizeof(a[0])) // 邻接矩阵 typedef struct _graph { char vexs[MAX]; // 顶点集合 int vexnum; // 顶点数 int edgnum; // 边数 int matrix[MAX][MAX]; // 邻接矩阵 }Graph, *PGraph; // 边的结构体 typedef struct _EdgeData { char start; // 边的起点 char end; // 边的终点 int weight; // 边的权重 }EData; /* * 返回顶点ch在matrix矩阵中的位置 */ static int get_position(Graph G, char ch) { int i; for (i = 0; i<G.vexnum; i++) if (G.vexs[i] == ch) return i; return -1; } /* * 创建图(用已提供的矩阵) */ Graph* create_example_graph() { char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; int matrix[][9] = { /*A*//*B*//*C*//*D*//*E*//*F*//*G*/ /*A*/{ 0, 12, INF, INF, INF, 16, 14 }, /*B*/{ 12, 0, 10, INF, INF, 7, INF }, /*C*/{ INF, 10, 0, 3, 5, 6, INF }, /*D*/{ INF, INF, 3, 0, 4, INF, INF }, /*E*/{ INF, INF, 5, 4, 0, 2, 8 }, /*F*/{ 16, 7, 6, INF, 2, 0, 9 }, /*G*/{ 14, INF, INF, INF, 8, 9, 0 } }; int vlen = LENGTH(vexs); int i, j; Graph* pG; // 输入"顶点数"和"边数" if ((pG = (Graph*)malloc(sizeof(Graph))) == NULL) return NULL; memset(pG, 0, sizeof(Graph)); // 初始化"顶点数" pG->vexnum = vlen; // 初始化"顶点" for (i = 0; i < pG->vexnum; i++) pG->vexs[i] = vexs[i]; // 初始化"边" for (i = 0; i < pG->vexnum; i++) for (j = 0; j < pG->vexnum; j++) pG->matrix[i][j] = matrix[i][j]; // 统计边的数目 for (i = 0; i < pG->vexnum; i++) for (j = 0; j < pG->vexnum; j++) if (i != j && pG->matrix[i][j] != INF) pG->edgnum++; pG->edgnum /= 2; return pG; } /* * 获取图中的边 */ EData* get_edges(Graph G) { int i, j; int index = 0; EData *edges; edges = (EData*)malloc(G.edgnum * sizeof(EData)); for (i = 0; i < G.vexnum; i++) { for (j = i + 1; j < G.vexnum; j++) { if (G.matrix[i][j] != INF) { edges[index].start = G.vexs[i]; edges[index].end = G.vexs[j]; edges[index].weight = G.matrix[i][j]; index++; } } } return edges; } /* * 对边按照权值大小进行排序(由小到大) */ void sorted_edges(EData* edges, int elen) { int i, j; for (i = 0; i<elen; i++) { for (j = i + 1; j<elen; j++) { if (edges[i].weight > edges[j].weight) { // 交换"第i条边"和"第j条边" EData tmp = edges[i]; edges[i] = edges[j]; edges[j] = tmp; } } } } /* * 获取i的终点 */ int get_end(int vends[], int i) { while (vends[i] != 0)//如果当前顶点为0，则返回自己 i = vends[i]; return i; } /* * 克鲁斯卡尔（Kruskal)最小生成树 */ void kruskal(Graph G) { int i, m, n, p1, p2; int length; int index = 0; // rets数组的索引 int vends[MAX] = { 0 }; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。 EData rets[MAX]; // 结果数组，保存kruskal最小生成树的边 EData *edges; // 图对应的所有边 // 获取"图中所有的边" edges = get_edges(G); // 将边按照"权"的大小进行排序(从小到大) sorted_edges(edges, G.edgnum); for (i = 0; i<G.edgnum; i++) { p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号 p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号 m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点 n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点 // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n rets[index++] = edges[i]; // 保存结果 } } free(edges); // 统计并打印"kruskal最小生成树"的信息 length = 0; for (i = 0; i < index; i++) length += rets[i].weight; printf("Kruskal=%d: ", length); for (i = 0; i < index; i++) printf("(%c,%c) ", rets[i].start, rets[i].end); printf("\n"); } int main() { Graph* pG; // 自定义"图"(输入矩阵队列) //pG = create_graph(); // 采用已有的"图" pG = create_example_graph(); kruskal(*pG); // kruskal算法生成最小生成树 return 0; }
此代码转载自wangkuiwu，虽然定义创建时有点绕，但是精华犹在。