如题；这是一套完整的可运行的代码；需要读者有一定的基础去阅读；
语言是用C语言实现；在C++环境中编写；在C++中可直接运行；在C语言中需要改部分头文件和输出语句；
头文件；这要是代码的声明部分；
# ifndef _ELGRAPH_ # define _ELGRAPH_ # include <iostream> using namespace std; # define MaxVertexNum 256 typedef char VertexType; typedef int WeightType; typedef struct EdgeNode { int vertex1; int vertex2; WeightType weight; }EdgeNode; typedef struct { VertexType vertex[MaxVertexNum]; EdgeNode edge[MaxVertexNum]; int vertexNum; int edgeNum; }ELGraph, * PELGraph; void CreateELGraph(PELGraph g); void SortELGraph(PELGraph g); void MiniSpanTreeKruskal(PELGraph g); # endif实现文件；主要是代码的实现；
# include "ELGraph.h" void CreateELGraph(PELGraph g) { return; } void SortELGraph(PELGraph g) { for (int i = 0; i < g->edgeNum - 1; i++) { for (int j = 0; j < g->edgeNum - 1 - i; j++) { //以权值为关键字对边表排序； if (g->edge[j].weight > g->edge[j + 1].weight) { //交换边表的元素； EdgeNode t = g->edge[j]; g->edge[j] = g->edge[j + 1]; g->edge[j + 1] = t; } } } return; } void MiniSpanTreeKruskal(PELGraph g) { //定义迭代变量并初始化； int i = 0; int j = 0; int k = 0; //定义保存边的数组；由于最小生成树的边数只有原图顶点数减一；用动态数组主要是因为不能使用变量定义静态数组； EdgeNode * array = (EdgeNode *)malloc((g->vertexNum - 1) * sizeof(EdgeNode)); //将每一个连通图的每一个顶点看成是一个连通分量；每一个连通分量设置一个编号；用动态数组主要是因为不能使用变量定义静态数组； int * flag = new int[g->vertexNum]; //设置编号； for (i = 0; i < g->vertexNum; i++) { flag[i] = i; } //按照每个边的权值由小到大排序；这里采用冒泡排序； SortELGraph(g); //倒数第二次就可以将全部的编号设置为相同；注意这里最后相同的编号对于不同的图可能不一样；与输入顺序有关； while (k < g->vertexNum - 1) { //检测是不是出于同一连通分量；避免形成回路； int s1 = flag[g->edge[j].vertex1]; int s2 = flag[g->edge[j].vertex2]; //不是同一连通分量； if (s1 != s2) { //将边保存到数组中方便后面统计信息； array[k].vertex1 = g->edge[j].vertex1; array[k].vertex2 = g->edge[j].vertex2; array[k].weight = g->edge[j].weight; //将另一个连通分量的编号变为另一个； for (i = 0; i < g->vertexNum; i++) { if (flag[i] == s2) { flag[i] = s1; } } //迭代变量自加； k++; } //不管是不是同一连通分量；j都要自加；因为他始终都要从边表中那到当前最小的边； j++; } //总权值； int u = 0; //遍历最小生成树中的所有边； for (int i = 0; i < g->vertexNum - 1; i++) { cout << array[i].vertex1 << "->" << array[i].weight<< "->" << array[i].vertex2 << ", " << endl; u += array[i].weight; } cout << "遍历编号数组的所有元素：" << endl; for (int i = 0; i < g->vertexNum; i++) { cout << flag[i] << endl; } return; }Main函数；
# include "ELGraph.h" int main(int argc, char ** arvv) { ELGraph g; g.vertexNum = 7; g.edgeNum = 10; for (int i = 0; i < g.vertexNum; i++) { g.vertex[i] = i; } g.edge[0].vertex1 = 0; g.edge[0].vertex2 = 1; g.edge[0].weight = 50; g.edge[1].vertex1 = 1; g.edge[1].vertex2 = 4; g.edge[1].weight = 40; g.edge[2].vertex1 = 4; g.edge[2].vertex2 = 5; g.edge[2].weight = 70; g.edge[3].vertex1 = 2; g.edge[3].vertex2 = 6; g.edge[3].weight = 45; g.edge[4].vertex1 = 2; g.edge[4].vertex2 = 0; g.edge[4].weight = 60; g.edge[5].vertex1 = 3; g.edge[5].vertex2 = 1; g.edge[5].weight = 65; g.edge[6].vertex1 = 3; g.edge[6].vertex2 = 4; g.edge[6].weight = 50; g.edge[7].vertex1 = 3; g.edge[7].vertex2 = 5; g.edge[7].weight = 30; g.edge[8].vertex1 = 3; g.edge[8].vertex2 = 6; g.edge[8].weight = 42; g.edge[9].vertex1 = 2; g.edge[9].vertex2 = 3; g.edge[9].weight = 52; MiniSpanTreeKruskal(&g); system("pause"); return 0; }