简介(最小生成树<->图连通)

eg:

村村通例子，把分散的村庄以最少的成本连接起来，做成连通图，有最少的边，每个边对应一条路。

此例子可以归纳为一个最小生成树的问题。

最小生成树存在，那么图一定是连通的，图连通的，那么最小生成树一定存在。

二者是充分必要条件。

而最小生成树包括三个概念:

树。

生成树。

最小生成树。

首先一棵树是连通的，一定没有回路。

有|V|个顶点的话，正好有|V|-1条边，不能多也不能少。

生成树:包含了全部的顶点，图中所有的顶点一定都要在这棵树中，|V|-1条边也肯定都在图中。

除第一张图外，其余三张图都是第一张图的子图，也就是说生成树不是唯一的，往其余三张图中加任何一条边都会构成回路，在树中构成回路是不可以的。

村庄之间有很多种修路方法，如何使这些边的权重和最小。

上述就是最小生成树的问题，解决其问题，可以归结为贪心算法。

贪心算法

解决问题是一步步来的，但在解决问题过程中每一步都要眼前最好的，这就是”贪”。

在不同问题中，”好”有不同的定义。

在最小生成树的问题中，所谓好就是每次都要一条权重最小边，这就叫”贪心”。

并不是把每条边按照权重排序，收购V-1条边就停止，没这么简单，看”下述约束”。

原图中没有的边是不能用的。

有|V|个顶点的话，正好有|V|-1条边，不能多也不能少。

当每条边收到集合中时，不能在现有树中构成回路，也要避免负值圈的现象。

8.1.1 贪心算法-Prim算法 (无向图-稠密图容易实现)

Prim算法的思想:从一个根结点开始，让一颗小数慢慢长大。

这里的前提条件:如果图比较稠密(完全图)。

1:首先在图中随意选一个V1结点作为根结点。

2:然后要找跟V1直接相关的三条边中找一条最小的，这条最小的边是要找跟这棵树有关系的往外能长出去的最小边。

这里把V4收录进来，这样树就有了两个顶点V1和V4。

3:这棵树继续往外长。此时以V1和V4为一棵树，找距离这棵树最小的边(而不是距离这棵树中某个结点的最小边的顶点)，此时可以选择的有V1-V2和V4-V3，先选这个V1-V2，此时，V2被收录进来，现在树中包括V1、V2、V4。

要注意V6-V7不与这棵树直接相连，不能收录。

4:收录V3进树，但V4-V2这条边是不能收录的，因为构成了V1-V2-V4的回路，V1-V3同理构成回路。

5:继续找最小的边。V4-V7。收录V7进树。

6:V7-V6。收录V6进树。

7:V7-V5。收录V5进树。

此时，全部7个顶点都收录进树中，六条边构成最小生成树。

8.1.1 Prim算法过程与Dijkstra算法差异(稠密图:O(|V|^2))

8.1.1 Prim算法源码(邻接表存储、收录边、结点、无回路计算)

#include<stdio.h>
/*
图-最小生成树问题-贪心算法-Prime算法-稠密图容易实现-邻接表存储-收录边和结点-与Dijkstra算法差异
*/
int main(void){
	return 0;
}
/* 返回未被收录顶点中dist最小者 */
Vertex FindMinDist(MGraph Graph, WeightType dist[]){

	Vertex MinV, V;
	WeightType MinDist = INFINITY;

	for(V = 0; V < Graph->Nv; V++){
	
		if(dist[V] != 0 && dist[V] < MinDist){
			/* 若V未被收录，且dist[V]更小 */
			MinDist = dist[V];/* 更新最小距离 */
			MinV = V;/* 更新对应顶点 */
		}
	
	}
	/* 若找到最小dist */
	if(MinDist < INFINITY){
		/* 返回对应的顶点下标 */
		return MinV;
	}
	/* 若这样的顶点不存在，返回-1作为标记 */
	else{
		return ERROR;
	}
}

/* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
int Prim(MGraph Graph, LGraph MST){

	WeightType dist[MaxVertexNum], TotalWeight;
	Vertex parent[MaxVertexNum], V, W;
	int VCount;

	Edge E;

	/* 初始化。默认初始点下标是0 */
	for(V = 0; V < Graph->Nv; V++){
		/* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */
		dist[V] = Graph->G[0][V];
		/* 暂且定义所有顶点的父结点都是初始点0 */
		parent[V] = 0;
	}

	/* 初始化权重和     */
	TotalWeight = 0;
	/* 初始化收录的顶点数 */
	VCount = 0;
	/* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
	MST = CreateGraph(Graph->Nv);
	/* 建立空的边结点 */
	E = (Edge)malloc(sizeof(struct ENode));

	/* 将初始点0收录进MST */
	dist[0] = 0;
	VCount++;
	/* 当前树根是0 */
	parent[0] = -1;

	while(1){
		/* 返回未被收录顶点中dist最小者 */
		V = FindMinDist(Graph, dist);
		/* V = 未被收录顶点中dist最小者 */
		if(V == ERROR){/* 若这样的V不存在 */
			break;/* 算法结束 */
		}
		/* 将V及相应的边<parent[V], V>收录进MST */
		E->V1 = parent[V];
		E->V2 = V;
		E->Weight = dist[V];
		InsertEdge(MST, E);
		TotalWeight += dist[V];
		dist[V] = 0;
		VCount++;
	}

	for(W = 0; W < Graph->Nv; W++){ /* 对图中的每个顶点W */
	
		if(dist[W] != 0 && Graph->G[V][W] < INFINITY){
			/* 若W是V的邻接点并且未被收录 */
			if(Graph->G[V][W] < dist[W]){
				/* 若收录V使得dist[W]变小 */
				dist[W] = Graph->G[V][W];/* 更新dist[W] */
				parent[W] = V;/* 更新树 */
			}
		}
	
	}

	/* MST中收的顶点不到|V|个 */
	if(VCount < Graph->Nv){
		TotalWeight = ERROR;
	}
	/* 算法执行完毕，返回最小权重和或错误标记 */
	return TotalWeight;

}

/* 初始化一个有VertexNum个顶点但没有边的图 */
LGraph CreateGraph(int VertexNum){
	Vertex V;
	LGraph Graph;
	/* 建立图 */
	Graph = (LGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
    /* 初始化邻接表头指针 */
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    for(V = 0; V < Graph->Nv; V++){
    	Graph->G[V].FirstEdge = NULL;
	}
	return Graph;
}

8.1.2贪心算法-Kruskal算法 (无向图-稀疏图容易实现)

这里的前提条件:如果图比较稀疏，有很多节点，但边条数比较少，差不多跟顶点数是同一数量级的，这种情况下更好的算法是Kruskal算法。

Kruskal算法的基本思想是将森林合并成树，比Prim更好理解。

什么叫做”将森林合并成树”？
认为每个顶点都是一棵树，通过不断把边收录进来，把两棵树合并成了一棵树，就逐渐把所有的结点合并成一棵树，这样就生成了最小生成树。

非常直截了当的贪心算法，每次就直接找权重最小的边把它收录进树中。

1:V1-V4和V6-V7的边权重最小，先收录V1-V4的边权重1。

2:收录V6-V7的边权重1。

3:收录V3-V4的边权重2。

4:收录V1-V2的边权重2。

(V2-V4的边权重3是可不收录的，因为V1-V2-V4构成了回路。V1-V3也不能收录。)

5:收录V4-V7的边权重4。

6:收录V5-V7的边权重6。

(V3-V6的边权重5是可不收录的，因为V3-V4-V6构成了回路。V4-V5和V2-V5也不能收录。)

此时，全部6条边都收录进树中，六条边构成最小生成树。

8.1.2 Kruskal算法过程(最小堆、并查集、稀疏图:O(|E|Log|E|))

8.1.2 Kruskal算法源码(邻接表存储、收录边、有回路计算)

#include<stdio.h>
/*
图-最小生成树问题-贪心算法-Kruskal算法-稀疏图容易实现-邻接表存储-收录边-最小堆和并查集处理边
*/
int main(void){
	return 0;
}

/*--------------------顶点并查集定义--------------------*/

typedef Vertex ElementType;/* 默认元素可以用非负整数表示 */
typedef Vertex SetName;/* 默认用根结点的下标作为集合名称 */
typedef ElementType SetType[MaxVertexNum];/* 假设集合元素下标从0开始 */

/* 初始化并查集 */
void InitializeVSet(SetType S, int N){
	ElementType X;
	for(X = 0; X < N; X++){
		S[X] = -1;
	}
}

/* 这里默认Root1和Root2是不同集合的根结点 */
void Union(){
	/* 保证小集合并入大集合 */
	if(S[Root2] < S[Root1]){/* 如果集合2比较大 */
		S[Root2] += S[Root1];/* 集合1并入集合2  */
		S[Root1] = Root2;
	}
	else{/* 如果集合1比较大 */
		S[Root1] += S[Root2];/* 集合2并入集合1  */
		S[Root2] = S[Root1];
	}
}

/* 默认集合元素全部初始化为-1 */
SetName Find(SetType S, ElementType X){
	if(S[X] < 0){
		/* 找到集合的根 */
		return X;
	}else{
		/* 路径压缩 */
		return S[X] = Find(S, S[X]);
	}
}

/* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */
bool CheckCycle(SetType VSet, Vertex V1, Vertex V2){
	Vertex Root1, Root2;
	/* 得到V1所属的连通集名称 */
	Root1 = Find(VSet, V1);
	/* 得到V2所属的连通集名称 */
	Root2 = Find(VSet, V2);
	/* 若V1和V2已经连通，则该边不能要 */
	if(Root1 == Root2){
		return false;
	}
	/* 否则该边可以被收集，同时将V1和V2并入同一连通集 */
	else{
		Union(VSet, Root1, Root2);
		return true;
	}
}

/*--------------------并查集定义结束--------------------*/

/*--------------------边的最小堆定义--------------------*/
/* 将图的边存入数组ESet，并且初始化为最小堆 */
void InitializeESet(LGraph Graph, Edge ESet){
	Vertex V;
	PtrToAdjVNode W;
	int ECount;
	/* 将图的边存入数组ESet */
	ECount = 0;
	for(V = 0; V < Graph->Nv; V++){
		for(W = Graph->G[V].FirstEdge; W; W = W->Next){
			/* 避免重复录入无向图的边，只收V1<V2的边 */
			if(V < W->AdjV){
				ESet[ECount].V1 = V;
				ESet[ECount].V2 = W->AdjV;
				ESet[ECount].Weight = W->Weight;
			}
		}
	}
	/* 初始化为最小堆 */
	for(ECount = Graph->Ne/2; ECount >= 0; ECount--){
		PercDown(ESet, ECount, Graph->Ne);
	}

}

/* 改编代码4.24的PercDown( MaxHeap H, int p )    */
/* 将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆 */
void PercDown(Edge ESet, int p, int N){

	int Parent, Child;
	struct ENode X;

	/* 取出根结点存放的值 */
	X = ESet[p];
	for(Parent = p; (Parent * 2 + 1) < N; Parent = Child){
		Child = Parent * 2 + 1;
		if((Child != N - 1) && (ESet[Child].Weight > ESet[Child + 1].Weight)){
			/* Child指向左右子结点的较小者 */
			Child++;
		}
		if(X.Weight <= ESet[Child].Weight){
			/* 找到了合适位置 */
			break;
		}else{
			/* 下滤X */
			ESet[Parent] = ESet[Child];
		}
	}
	ESet[Parent] = X;
}

/* 给定当前堆的大小CurrentSize，将当前最小边位置弹出并调整堆 */
int GetEdge(Edge ESet, int CurrentSize){
	/* 将最小边与当前堆的最后一个位置的边交换 */
	Swap(&ESet[0], &ESet[CurrentSize - 1]);
	/* 将剩下的边继续调整成最小堆 */
	PercDown(ESet, 0, CurrentSize - 1);
	/* 返回最小边所在位置 */
	return CurrentSize - 1;
}

/*--------------------最小堆定义结束--------------------*/

/* 
将最小生成树保存为邻接表存储的图MST，返回最小权重和 
*/
int Kruskal(LGraph Graph, LGraph MST){

	WeighType TotalWeight;
	int ECount, NextEdge;
	/* 顶点数组 */
	SetType VSet;
	/* 边数组 */
	Edge ESet;
	/* 初始化顶点并查集 */
	InitializeVSet(VSet, Graph->Nv);
	ESet = (Edge)malloc(sizeof(struct ENode) * Graph->Ne);
	/* 初始化边的最小堆 */
	InitializeESet(Graph, ESet);
	/* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
	MST = CreateGraph(Graph->Nv);
	/* 初始化权重和     */
	TotalWeight = 0;
	/* 初始化收录的边数 */
	ECount = 0;
	/* 原始边集的规模 */
	NextEdge = Graph->Ne;
	/* 当收集的边不足以构成树时 */
	while(ECount < Graph->Nv - 1){
		/* 从边集中得到最小边的位置 */
		NextEdge = GetEdge(ESet, NextEdge);
		/* 边集已空 */
		if(NextEdge < 0){
			break;
		}
		/* 如果该边的加入不构成回路，即两端结点不属于同一连通集 */
		if(CheckCycle(VSet, ESet[NextEdge].V1, ESet[NextEdge].V2) == true){
			/* 将该边插入MST */
			InsertEdge(MST, ESet + NextEdge);
			/* 累计权重 */
			TotalWeight += ESet[NextEdge].Weight;
			/* 生成树中边数加1 */
			ECount++;
		}
	}
	if(ECount < Graph->Nv - 1){
		/* 设置错误标记，表示生成树不存在 */
		TotalWeight = -1;
	}

	return TotalWeight;
}

/* 初始化一个有VertexNum个顶点但没有边的图 */
LGraph CreateGraph(int VertexNum){
	Vertex V;
	LGraph Graph;
	/* 建立图 */
	Graph = (LGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
    /* 初始化邻接表头指针 */
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    for(V = 0; V < Graph->Nv; V++){
    	Graph->G[V].FirstEdge = NULL;
	}
	return Graph;
}