最小生成树Prim算法跟单源最短路径Dijkstra算法

最小生成树Prim算法和单源最短路径Dijkstra算法

问题：

1. （最小生成树）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，即求最小生成树。

2. （单源最短路径）给定一个权值都为正数的无向连通图和一个源点，确定它到其它点的最短距离。

之所以将这两个问题放在一起，是因为Prim算法与Dijkstra算法的思路和程序都非常相似，都是有贪心策略。

1.解法（Prim算法）：

思路：设连通网络 N = { V, E }，U表示已加入到生成树的顶点集合。在初始化阶段，任取一个顶点，用其关联边的权值作为初始的V-U顶点集合的数据。在每一步中，先在V-U顶点集合中选择距离U中任意点“最近”的顶点v，再把v加入到U中，最后看看在新的V-U顶点集合中，是否有哪个顶点距离v比距离U中其它点更近，若有则更新V-U顶点集合中的数据。U的元素个数为V-1，所以共要进行V-1步。

总的时间复杂度为Time = O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY

若用数组作为顶点权值的数据结构，T_EXTRACT-MIN用时O(V)，T_DECREASE-KEY用时O(1)，总共用时O(V^2)

若用最小堆作为顶点权值的数据结构，T_EXTRACT-MIN用时O(lgV)，T_DECREASE-KEY用时O(lgV)，总共用时O((V+E)*lgV)

若用斐波那契堆作为顶点权值的数据结构，T_EXTRACT-MIN平均用时O(lgV)，T_DECREASE-KEY平均用时O(1)，总共用时O(E+V*lgV)

下面的代码使用数组作为顶点权值的数据结构：

#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 1001
#define INF  1000000

int lowcost[MAXN];	// 距离U中顶点的最小权值
bool visited[MAXN];	// 若为true表示已加入到集合U中
int mst[MAXN];		// 距离U中哪个顶点最短
int graph[MAXN][MAXN];	// 用矩阵表示图上各边权值

void Prim(int n)
{
	int i, j;
	memset(visited, 0, n*sizeof(bool));
	visited[0] = true;
	mst[0] = -1;
	for (i=1; i<n; i++)
	{
		lowcost[i] = graph[0][i];
		mst[i] = 0;
	}
	for (i=1; i<=n-1; i++)
	{
		// 取V-U中的最小权值T_EXTRACT-MIN O(V)
		int min=INF, minid;
		for (j=1; j<n; j++)
			// 用visited数组确定V-U
			if (!visited[j] && lowcost[j] < min)
			{
				min = lowcost[j];
				minid = j;
			}
		visited[minid] = true;
		// 减小V-U中的权值T_DECREASE-KEY O(1)
		for (j=1; j<n; j++)
			if (!visited[j] && lowcost[j] > graph[minid][j])
			{
				lowcost[j] = graph[minid][j];
				mst[j] = minid;
			}
	}
}

int main()
{
	int n, m, i, j;
	cin >> n >> m;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
			graph[i][j] = INF;
	for (i=0; i<m; i++)
	{
		char a[3], b[3];
		int c;
		scanf("%s %s %d",&a, &b, &c);
		graph[a[0]-'A'][b[0]-'A'] = c;
		graph[b[0]-'A'][a[0]-'A'] = c;
	}
	Prim(n);
	int total = 0;
	for (i=1; i<n; i++)
	{
		total += lowcost[i];
		printf("%c-%c: %d\n", i+'A', mst[i]+'A', lowcost[i]);
	}
	printf("%d\n", total);
}

2.解法（Dijkstra算法）：

思路：设连通网络 N = { V, E }和给定源点u，U表示已确定最短路径的顶点集合。在初始化阶段，用顶点u所关联边的权值作为初始的V-U顶点集合的数据。在每一步中，先在V-U顶点集合中选择距离源点u“最近”的顶点v，再把v加入到U中，最后看看在新的V-U顶点集合中，是否有哪个顶点通过顶点v到达源点u比通过U中其它点到达距离更短，若有则更新V-U顶点集合中的数据。U的元素个数为V-1，所以共要进行V-1步。