(C/C++)-最小生成樹演算法(Prim&Kruskal)和單源最短路徑演算法(Dijkstra)

(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;
}