(C/C++)-最小生成树算法(Prim&Kruskal)和单源最短路径算法(Dijkstra)

1、什么是最小生成树

对于一个带权连通无向图G=(V,E)，图G的不同的生成树，其所对应的生成树的权值可能不同。设R是G所有生成树的集合，T是R中权值最小的那棵生成树，则称T为G的最小生成树

最小生成树的性质

• 最小生成树可能不唯一，但其对应的边的权值之和总是唯一的，且是最小的；
• 最小生成树的边数为顶点数-1；

---

2、Prim算法的实现(选点)

图G=(V,E)，其中V为所有结点的集合，E为图G的边的集合
用辅助集合s，来描述被选中的顶点

思路：

• 首先将第一个顶点放入集合s中，即s={1}；
• 做如下贪心选择，当s是v的真子集时，选取i属于s，j属于V-S，且c[i][j]是最小的边，并将顶点j加入到集合s中；
• 当S=V时选取结束，此时就生成了一棵最小生成树；

如图所示，描述了Prim算法选取顶点的过程：

具体实现过程：

void prim(int c[N][N], int n)
{
	int lowcost[N];//存储非集合s顶点到集合s中顶点最小边的权值
	int closest[N];//存储非集合s顶点到集合s中权值最小边的顶点
	int s[N];

	s[1] = 1;
	printf("1 ");

	//lowcost[]和closest[]的初始化
	for (int i = 2; i < N; i++)
	{
		closest[i] = 1;
		lowcost[i] = c[1][i];
		s[i] = 0;
	}

	//每次循环箱集合s中添加一个顶点
	for (int i = 2; i < N; i++)
	{
		int min = maxint;
		int temp = 1;//用来记录选择的顶点

		//做贪心选择，选择非集合s中顶点到s中顶点最小的权值边的顶点
		for (int j = 2; j < N; j++)
			if (!s[j] && min > lowcost[j])
			{
				//更新值,并记录
				min = lowcost[j];
				temp = j;
			}

		s[temp] = 1;//顶点加入到集合s
		printf("%d ", temp);

		//更新lowcost[]和closest[]
		for(int j=2;j<N;j++)
			if (!s[j] && lowcost[j] > c[j][temp])
			{
				lowcost[j] = c[j][temp];
				closest[j] = temp;
			}
	}
}

在main()函数中测试一下Prim算法：

int main()
{
	int c[N][N] = {//0号下标不用
		{maxint,maxint,maxint,maxint,maxint,maxint,maxint},//0
		{maxint,maxint,6,1,5,maxint,maxint},//1
		{maxint,6,maxint,5,maxint,3,maxint},//2
		{maxint,1,5,maxint,5,6,4},//3
		{maxint,5,maxint,5,maxint,maxint,2},//4
		{maxint,maxint,3,6,maxint,maxint,6},//5
		{maxint,maxint,maxint,4,2,6,maxint}//6
	};

	printf("Prim点选取顺序为:\n");
	prim(c, N);

	return 0;
}

---

3、Kruskal算法的实现(选边)

图G=(V,E)，其中V为所有结点的集合，E为图G的边的集合

采用Kruskal算法时，采用了并查集作为辅助的数据结构
并查集中两个重要的实现函数：

• int find_root(int x)：查找以结点x的根结点；
• int union_set(int x,int y):合并x，y所在的两个子集，若两个子集存在回路返回0，不存在回路返回1；

思路：

• 将图G的边集按照权值大大小升序排列
• 每次选取未被选取过，且权值最小的边，若选取该边构成回路，则舍弃该边，选择下一条权值最小的边；
• 直到图G所有的顶点在一个连通分量上；

如图所示，描述了Kruskal算法选取顶点的过程：

具体实现过程：

边的结构体

typedef struct edge
{
	int x;
	int y;
	int weight;
	char name;
	int selected;
}Edge;

并查集的函数

int parent[N];//记录顶点的父结点
int rank[N];//记录以顶点为根的树的深度(压缩路径)

//初始化parent[]和rank[]
void init()
{
	for (int i = 1; i < N; i++)
	{
		parent[i] = -1;//初始时，每个顶点的父结点默认为-1
		rank[i] = 1;
	}
}

//查找顶点x的根结点
int find_root(int x)
{
	int x_root = x;
	while (parent[x_root] != -1)
		x_root = parent[x_root];
	return x_root;
}

//合并两个顶点所在的子集，合并成功返回1，失败返回0
int union_set(int i, int j)
{
	int i_root = find_root(i);
	int j_root = find_root(j);

	if (i_root == j_root)
		return 0;//i,j在同一个子集中，合并失败

	//i,j不在同一个子集中，合并两个子集
	if (rank[i_root] > rank[j_root])
		parent[j_root] = i_root;
	else if (rank[i_root] < rank[j_root])
		parent[i_root] = parent[j_root];
	else
	{
		//i,j深度相同的情况下
		parent[i_root] = j_root;
		rank[j_root]++;
	}
	return 1;
}

Kruskal实现

//n是边的个数
void kruskal(Edge e[], int n)
{
	init();
	qsort(e, 11, sizeof(e[1]), cmp);//升序

	for (int i = 1; i <= n; i++)
	{
		int x = find_root(e[i].x);
		int y = find_root(e[i].y);

		if (x != y)
		{
			//无回路，选中此边
			e[i].selected = 1;
			union_set(e[i].x, e[i].y);
			printf("%c ", e[i].name);
		}
	}
	/*
	for (int i = 1; i <= n; i++)
		if (e[i].selected)
			printf("%c ", e[i].name);*/
}

测试函数

int main()
{
	Edge e[11] = {//10条边
		{0},//此条数据不用
		{1,4,5,'a',0},{4,6,2,'b',0},{6,5,6,'c',0},{5,2,3,'d',0},{2,1,6,'e',0},
		{1,3,1,'f',0},{3,4,5,'g',0},{3,6,4,'h',0},{3,5,6,'i',0},{3,2,5,'j',0}
	};

	int n = 10;

	kruskal(e, n);

	return 0;
}

---

4、Dijkstra算法的实现(选点)

图G=(V,E)，其中V为所有结点的集合，E为图G的边的集合

采用辅助数组dist[i]，来存储从源点到i的最短距离

思路：

• 从集合V-S中选取顶点j，满足dist[j]=min{dist[i]|i属于V-S}，并将顶点j加入到集合s中
• 集合s扩充后，修改源点出发到V-S上任一顶点k的最短路径，dist[j]+c[j][k]<dist[k](这里是Dijkstra区别于Prim的最重要一点)
• 重复上述步骤，知道所有顶点都在集合S中

如图示

具体实现：

//dist[i]存储从源点到i的最短路径
void dijkstra(int c[][N], int dist[], int start)
{
	int s[N];

	//初始化参数
	for (int i = 1; i < N; i++)
	{
		dist[i] = c[start][i];
		s[i] = 0;
	}
	s[start] = 1;

	//每次循环箱集合s中添加一个顶点
	for (int i = 2; i < N; i++)
	{
		int tmp = maxint;
		int u = start;

		//做贪心选择，选择非集合s中顶点到源点最小的权值边的顶点
		for (int j = 1; j < N; j++)
		{
			if (!s[j] && dist[j] < tmp)
			{
				//记录
				u = j;
				tmp = dist[j];
			}
		}

		s[u] = 1;

		//更新dist[]的值
		for (int j = 1; j < N; j++)
			if (!s[j] && (dist[u] + c[u][j] < dist[j]))
				dist[j] = dist[u] + c[u][j];

	}
}

main函数中的测试：

int main()
{
	int c[N][N] = {
		{0},//0号下标不使用
		{0,0,10,maxint,maxint,5},
		{0,maxint,0,1,maxint,2},
		{0,maxint,maxint,0,4,maxint},
		{0,7,maxint,6,0,maxint},
		{0,maxint,3,9,2,0}
	};//5个顶点,0号下标不使用

	int dist[N], start = 1;

	dijkstra(c, dist, start);

	for (int i = 1; i < N; i++)
		printf("dist[%d]=%d\t", i, dist[i]);
	printf("\n");

	return 0;
}

---