数据结构–图 –最小生成树
1.基本概念
生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。
最小生成树：我们把构造连通网的最小代价生成树称为最小生成树。（一棵生成树的代价就是树上各边的代价之和）
2.经典的两种算法
2.1 Prim算法思路
假设全部顶点的集合是V，已经被挑选出来的是U，那么从集合V-U中不断挑选权值最低的点。（这里的权值最低，是相对于U中所有的点来说，是把U看成一个整体。Prim算法和后面的求最短路径的Dijkstra算法有些相似，具体区别看2.3（Prim算法和Dijkstra算法比较））。
以某起点为顶点，逐步找各顶点上最小权值的边来构建最小生成树。（这就像是我们如果去参观某个展会，例如世博会，你从一个入口进去，然后找你所在位置周边的场馆中你最感兴趣的场馆观看，看完后再用同样的办法看下一个）
2. 2 Kruskal算法思路
从宏观着眼，将所有的边排成序列，依次从小到大找边来构建最小生成树。若加入某条边构成回路则舍弃这条边。（这就像是我们参观世博会，事先计划好，进园后直接去到最想看的场馆观看）
2.3
Prim算法与Kruskal算法比较：
Prim算法主要针对顶点展开的，对于稠密图，即边数非常多的情况会更好一些；
Kruskal算法主要针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势。
Prim算法与Dijkstra算法比较[转]1：
在图论中，Prim算法是计算最小生成树的算法，而Dijkstra算法是计算最短路径的算法。二者看起来比较类似，因为假设全部顶点的集合是V，已经被挑选出来的点的集合是U，那么二者都是从集合V-U中不断的挑选权值最低的点加入U，那么二者是否等价呢？也就是说是否Dijkstra也可以计算出最小生成树而Prim也可以计算出从第一个顶点v0到其他点的最短路径呢？答案是否定的，否则就不必有两个算法了。
二者的不同之处在于“权值最低”的定义不同，Prim的“权值最低”是相对于U中的任意一点而言的，也就是把U中的点看成一个整体，每次寻找V-U中跟U的距离最小（也就是跟U中任意一点的距离最小）的一点加入U；而Dijkstra的“权值最低”是相对于v0而言的，也就是每次寻找V-U中跟v0的距离最小的一点加入U。
一个可以说明二者不等价的例子是有四个顶点(v0, v1, v2, v3)和四条边且边值定义为(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的图，用Prim算法得到的最小生成树中v0跟v1是不直接相连的，也就是在最小生成树中v0v1的距离是v0->v2->v3->v1的距离是27，而用Dijkstra算法得到的v0v1的距离是20，也就是二者直接连线的长度。
3.算法实现
- Prim算法
- Kruskal算法
4.代码实现
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define OVERFLOW -2
#define MAX_VERTEX_SIZE 20
#define INFINITY 65535
typedef int Status;
typedef int VertexType; //顶点类型
typedef int VRType; //顶点关系类型
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef struct VNode
{
VertexType data;
}VNode,AdjList[MAX_VERTEX_SIZE];
typedef struct ArcCell
{
VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
typedef struct
{
int vexnum,arcnum;
AdjMatrix arcs;
AdjList vertices;
GraphKind kind;
}MGraph;
typedef struct Edge // MiniSpanTree_Kruskal算法专用
{
int begin;
int end;
int weight;
}Edge;
Status CreateGraph(MGraph *G){
VNode v1,v2;
int i,j,sign1,sign2;
int value;
(*G).kind = UDN;
printf("输入顶点数、弧的数\n");
scanf("%d%d",&(*G).vexnum, &(*G).arcnum);
for(i = 0; i < (*G).vexnum; ++i){
for(j = 0; j < (*G).vexnum; ++j){
if(i == j)
(*G).arcs[i][j].adj = 0;
else
(*G).arcs[i][j].adj = INFINITY;
}
}
printf("初始化顶点\n");
for(i = 0; i < (*G).vexnum; ++i){
scanf("%d",&(*G).vertices[i].data);
}
printf("初始化弧\n");
for(i = 0; i < (*G).arcnum; ++i){
sign1 = -1;
sign2 = -1;
scanf("%d%d%d",&v1.data,&v2.data,&value);
for(j = 0; j < (*G).vexnum; ++j){
if(v1.data == (*G).vertices[j].data)
sign1 = j;
if(v2.data == (*G).vertices[j].data)
sign2 = j;
}
(*G).arcs[sign1][sign2].adj = value;
(*G).arcs[sign2][sign1].adj = value;
}
return OK;
}
void test(MGraph G){ //测试函数，打印创建好的邻接矩阵
int i,j;
for(i = 0; i < G.vexnum; ++i){
for(j = 0; j < G.vexnum; ++j)
printf("%.6d ",G.arcs[i][j]);
printf("\n");
}
}
Status MiniSpanTree_Prim(MGraph G){
int i,j,k,min;
int adjvex[G.vexnum];
int lowcost[G.vexnum];
for(i = 0; i < G.vexnum; ++i){ //初始化
lowcost[i] = G.arcs[0][i].adj;
adjvex[i] = 0;
}
lowcost[0] = 0;
for(i = 1; i < G.vexnum; ++i){ //找出lowcost[]中的最小值
min = INFINITY;
for(j = 1; j < G.vexnum; ++j){
if(lowcost[j] != 0 && lowcost[j] < min){
min = lowcost[j];
k = j;
}
}
lowcost[k] = 0;
printf("(%d, %d)\n",adjvex[k],k);
for(j = 1; j < G.vexnum; ++j){ //更新lowcost[]和adjvex[]
if(lowcost[j] != 0 && G.arcs[k][j].adj < lowcost[j]){
lowcost[j] = G.arcs[k][j].adj;
adjvex[j] = k;
}
}
}
return OK;
}
Edge* CreateEdges(MGraph G){ //MiniSpanTree_Kruskal算法子函数：对边按权值从小到大的顺序排序
int i,j;
int k = 0;
Edge temp;
Edge *p;
p = (Edge *)malloc(G.arcnum * sizeof(Edge));
if(!p)
exit(OVERFLOW);
for(i = 0; i < G.vexnum; ++i){ //初始化
for(j = i; j < G.vexnum; ++j){
if(G.arcs[i][j].adj != 0 && G.arcs[i][j].adj != INFINITY){
p[k].begin = i;
p[k].end = j;
p[k].weight = G.arcs[i][j].adj;
++k;
}
}
}
for(i = 0; i < G.arcnum-1; ++i){ //按权值从小到大排序
for(j = i + 1; j < G.arcnum; ++j){
if(p[i].weight > p[j].weight){
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}
return p;
}
Status MiniSpanTree_Kruskal(MGraph G){
Edge *edges;
int parent[G.vexnum];
int i,m,n;
edges = CreateEdges(G);
for(i = 0; i < G.vexnum; ++i) //初始化
parent[i] = 0;
for(i = 0; i < G.arcnum; ++i){ //循环每一条边
n = Find(parent,edges[i].begin);
m = Find(parent, edges[i].end);
if(n != m){ //若n与m不等，则说明此边没有与现有生成树形成回路
parent[n] = m;
printf("(%d,%d) %d\n",edges[i].begin, edges[i].end, edges[i].weight);
}
}
return OK;
}
int Find(int *parent,int f){ //MiniSpanTree_Kruskal算法子函数 查找连线顶点的尾部下标
while(parent[f] > 0)
f = parent[f];
return f;
}
int main(){
MGraph G;
Edge *edges;
int i;
CreateGraph(&G);
printf("创建的邻接矩阵如下：\n");
test(G);
printf("MiniSpanTree_Prim:\n");
MiniSpanTree_Prim(G);
//MiniSpanTree_Kruskal算法
printf("将边按权值从小到大排序如下\n");
edges = CreateEdges(G);
for(i = 0; i < G.arcnum; ++i){
printf("%d %d %d \n",edges[i].begin, edges[i].end, edges[i].weight);
}
printf("MiniSpanTree_Kruskal\n");
MiniSpanTree_Kruskal(G);
return 0;
}
参考资料：
1.严蔚敏 数据结构 清华大学出版社
2.程杰 大话数据结构 清华大学出版社
3.http://www.cnblogs.com/huiliu/archive/2011/04/15/2017228.html