求圖的最小生成樹

上一小節讨論了一些圖的基本概念。其中提到，如果有兩幅圖G=(V,E)，G'=(V',E')，如果V'∈V,E'∈E，則稱G'是G的子圖。如果V'=V，且E'∈E（即頂點不少，邊少了幾條），那麼G'是G的生成子圖。特别的，如果生成子圖是一棵樹，即滿足定點數 = 邊樹+1，那麼這棵樹稱為生成樹。

最小生成樹的概念是基于“帶權圖”的。即圖中每條邊上都有特定的權值，這樣的圖又稱為網。最小生成樹指的是所有生成樹中，權值之和最小的樹。

當然，這個概念絕非數學家們自己胡思亂想出來的，它能對很多實際的問題模組化：比如有A，B，C，D，E，F，6個地方。我們需要修路讓他們之間可以互相連通。但是各個節點之間修路的花費可能不一樣，n個地方如果兩兩相通，一共有n(n-1)/2條路，我們想在其中找出n-1條，讓它們的花費最小。那麼如何選擇出這n-1條路徑呢？有兩種經典的算法Kruskal算法和Prim算法。

先看定義的一些基本的資料結構（總體上跟圖的差不多）

#include <stdio.h>
#include <limits.h>
#include <malloc.h>
#define MAX 10
//帶權圖的基本資料結構
typedef int** adjacentMatrix;

typedef struct WeightedGraph
{
	adjacentMatrix matrix;
	char* vertex;
	int vertexNumber;
	int arcNumber;
}wGraph;

//基本操作聲明
//初始化圖
wGraph initWgraph(int );
//銷毀圖
void destroyWgraph(wGraph*);
//增加一條邊
bool addArc(wGraph* ,char ,char ,int );
//删除一條邊
bool deleteArc(wGraph* ,char ,char );
//顯示鄰接矩陣
void printfWgraph(wGraph* );

//Kruskal算法相關函數
int findMiniWeightArc(wGraph* ,char*,char*);
void do_dfs(wGraph* ,int );
bool is_loop(wGraph* );
void Kruskal(wGraph* ,wGraph* );

Kruskal算法的基本思路如下：

1.将圖的邊集合按照權值大小排序（可選）。

2.從E中挑出一個權值最小的邊e，權值為we

3.将e加入到生成樹的邊的集合T中。

4.加入e之後判斷T是否形成回路

5.若T的邊數<n-1，則轉2，否則退出

程式如下：

wGraph initWgraph(int n)
{
	wGraph g;
	g.vertexNumber = n;
	g.arcNumber = 0;
	g.vertex = (char*)malloc(sizeof(char) * n);
	char start = 'A';
	for(int i = 0; i < n;++i)
		g.vertex[i] = start + i;

	g.matrix = (int**)malloc(sizeof(int*) * n);
	for(int i = 0; i < n;++i)
		g.matrix[i] = (int*)malloc(sizeof(int) * n);
	//鄰接矩陣的初始為為最大值
	for(int i = 0; i < n;++i)
		for(int j = 0; j < n;++j)
			g.matrix[i][j] = INT_MAX;
	return g;
}

void destroyWgraph(wGraph* g)
{

	free(g->vertex);
	g->vertex = NULL;
	for(int i = 0; i < g->vertexNumber;++i)
		free(g->matrix[i]);
	free(g->matrix);
	g->matrix = NULL;
	g->arcNumber = -1;
	g->vertexNumber = -1;
}

bool addArc(wGraph* g,char vertex1,char vertex2,int weight)
{
	int i = vertex1 - 'A';
	int j = vertex2 - 'A';
	if(i < 0 || i > g->vertexNumber || j < 0 || j > g->vertexNumber)
	{
		printf("vertexes does not exsist!\n");
		return false;
	}
	else
	{
		g->matrix[i][j] = g->matrix[j][i] = weight;	
		g->arcNumber++;
		return true;
	}

}

bool deleteArc(wGraph* g,char vertex1,char vertex2)
{
	int i = vertex1 - 'A';
	int j = vertex2 - 'A';
	if(i < 0 || i > g->vertexNumber || j < 0 || j > g->vertexNumber)
	{
		printf("vertexes does not exsist!\n");
		return false;
	}
	if(INT_MAX == g->matrix[i][j] )
	{
		printf("there is no arc between vertexes!\n");
		return false;
	}
	else
	{
		g->matrix[i][j] = INT_MAX;
		g->matrix[j][i] = INT_MAX;
		g->arcNumber--;
		return true;
	}
}

void printfWgraph(wGraph* g)
{
	printf("     ");
	for(int i = 0 ; i < g->vertexNumber;++i)
		printf("%-4c ",g->vertex[i]);

	for(int i = 0; i < g->vertexNumber;++i)
	{
		printf("\n");
		printf("%-4c ",g->vertex[i]);
		for(int j = 0; j < g->vertexNumber;++j)
		{
			if(INT_MAX == g->matrix[i][j]  )
				printf("NULL ");
			else
				printf("%-4d ",g->matrix[i][j]);
		}
			
	}
	printf("\n");
}
//找完以後需要打上标記，否則下一次還會找他
int findMiniWeightArc(wGraph* g,char *vertex1,char *vertex2)
{
	int miniWeight = INT_MAX;
	int vex1;
	int vex2;
	for(int i = 0; i < g->vertexNumber;++i)
	{
		for(int j = 0; j< g->vertexNumber;++j)
		{
//			printf("測試邊%c%c，它的權值為%d\n",g->vertex[i],g->vertex[j],g->matrix[i][j]);
			if(g->matrix[i][j] < miniWeight && g->matrix[j][i] < miniWeight && g->matrix[i][j] != -1 && g->matrix[j][i] != -1)
			{
				miniWeight = g->matrix[i][j];
				vex1 = i;
				vex2 = j;
			}
		}
	}
	//打上标記
	g->matrix[vex1][vex2] = -1;
	g->matrix[vex2][vex1] = -1;
	*vertex1 = 'A' + vex1;
	*vertex2 = 'A' + vex2;
	return miniWeight;
}

//判斷加入以後是否形成回路
//visit1表明該節點是否被通路過
bool visit1[MAX];
//visit2表明該節點在這次搜尋中是否被通路過
bool visit2[MAX][MAX];
bool LOOP = false;

void do_dfs(wGraph* g,int i)
{
	visit1[i] = true;
	
	for(int j = 0; j < g->vertexNumber;++j)
	{
		//對目前節點，挑選可以通路的節點
		if(INT_MAX != g->matrix[i][j])
		{
			//如果這個次通路為回溯，則跳過這個節點
			if(visit2[i][j] == true)
				continue;
			else
			{
				if(visit1[j] == false)
				{
					visit2[i][j] = true;
					visit2[j][i] = true;
					do_dfs(g,j);
				}
				else
					LOOP = true;

			}
		}

	}
}

bool is_loop(wGraph* g)
{
	//重置LOOP
	LOOP = false;
	//

	for(int i = 0; i < g->vertexNumber;++i)
	{
		visit1[i] = false;
		
	}
	for(int i = 0; i < g->vertexNumber;++i)
	{
		for(int j = 0; j < g->vertexNumber;++j)
		{
			visit2[i][j] = false;
		}
	}
	for(int i = 0; i < g->vertexNumber;++i)
	{
		if(false == visit1[i])
			do_dfs(g,i);
	}

	return LOOP;
}

void Kruskal(wGraph* g,wGraph* tree)
{	
	//先初始化樹
	*tree = initWgraph(g->vertexNumber);
	while(tree->arcNumber < g->vertexNumber-1)
	{
		char vertex1;
		char vertex2;
		int weight = findMiniWeightArc(g,&vertex1,&vertex2);
		addArc(tree,vertex1,vertex2,weight);
		if(is_loop(tree) == true)
		{
			printf("被删除的邊為：%c,%c\n",vertex1,vertex2);
			deleteArc(tree,vertex1,vertex2);
			
		}
		else
			printf("挑出來的邊為：%c,%c\n",vertex1,vertex2);
//		printfWgraph(tree);
	}
}

再看Prim算法：

1.設頂點集合為V，從V中任取一個頂點，加入U中，并将這個節點從V中删去。

2.在U與V構成的所有邊中，選擇一個權值最小的，加入樹的邊集合E

3.将邊E的另一個節點vx也加入集合U中。

4.若V不為空，則轉2

//Prim算法相關的函數
void selectMiniWeightArc(wGraph* g,bool* u,bool* v,int* indexV,int* indexU);
void Prim(wGraph* g,wGraph* t,char Start);

void Prim(wGraph* g,wGraph* t,char Start)
{
	
	//将t初始化
	*t = initWgraph(g->vertexNumber);
	bool *V  = (bool*)malloc(sizeof(bool) * g->vertexNumber);
	//V集合初始值為true表示這個集合裡的元素都可用，false表示集合中元素被删掉了
	for(int i = 0; i < g->vertexNumber;++i)
		V[i] = true;
	int cnt = g->vertexNumber; 
	bool *U = (bool*)malloc(sizeof(bool) * g->vertexNumber);
	//U集合初始值為false，表明這個集合中還沒有任何元素，true表示這個元素可用
	for(int i = 0; i < g->vertexNumber;++i)
		U[i] = false;
	//每次從V中選中一個元素，則把它的V[i]設為false,把U[i]設為true
	int start = Start-'A';
	V[start] = false;
	--cnt;
	U[start] = true;
	while(cnt >0)
	{
		int indexV;
		int indexU;
		//在U與V-U中尋找權值最小的邊
		selectMiniWeightArc(g,U,V,&indexV,&indexU);
		char vertex1 = indexV+'A';
		char vertex2 = indexU+'A';
//		printf("挑出V中的節點%c，U中的節點%c\n",vertex1,vertex2);
		addArc(t,vertex1,vertex2,g->matrix[indexV][indexU]);
		V[indexU] = false;
		U[indexU] = true;
		--cnt;

	}
	free(U);
	free(V);
}


void selectMiniWeightArc(wGraph* g,bool* u,bool* v,int* indexV,int* indexU)
{
	int min = INT_MAX;
	//列印一下兩個數組的現狀
	printf("V:");
	for(int i = 0; i < g->vertexNumber;++i)
		printf("V[%d] = %d  ",i,v[i]);
	printf("\n");
	printf("U:");
	for(int i = 0; i < g->vertexNumber;++i)
		printf("U[%d] = %d  ",i,u[i]);
	printf("\n");
	//周遊整個圖
	for(int i = 0; i < g->vertexNumber;++i)
	{
		for(int j = 0; j < g->vertexNumber;++j)
		{
			//i是V中的，j是U中的
			if(false == v[i] && true == u[i] && true == v[j] && false == u[j])		
				
			{
				if(g->matrix[i][j] < min)
				{
					min = g->matrix[i][j];
					*indexV = i;
					*indexU = j;
				}
			}
		}
	}
}

程式中需要注意，當兩個頂點不連通是，我對他們之間的權值設定為INT_MAX，但是在列印時，為了好看一點，顯示NULL。具體的算法程式是嚴格按照算法的步驟寫的，基本沒有什麼花架子。唯一需要說明的是，在Kruskal算法中，需要檢測是否形成回路回路，這個問題可讓我費了一番周折。因為沒有學過離散數學，是以也沒有用什麼好的辦法，而是用了一個比較樸素的辦法：深度優先周遊整個圖：從A找到C以後，把A->C與C->A的兩條路都标記了起來。然後繼續向下查找，如果最後能找回來，則說明有回路。

具體的查找過程可以通過注釋起來的列印資訊看出來，這裡就不羅嗦了。

最後簡單的比較這兩種算法：Prim算法使用的資料結構稍微有點複雜，用兩個數組記錄了頂點是否被使用過，但是它很好地避免了回路檢測這個問題；而Kruskal算法則上手比較容易，更符合我們的基本思維，但是回路檢測過程卻效率低下（這也與我的回路檢測算法有關）。總體上來說，Prim算法跟勝一籌。

求圖的最小生成樹

繼續閱讀

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

C++ 第十五周報告1--《冒泡法排序》

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

QR碼編碼原理三（日本漢字和中文編碼）

Linux裝置模型（中）之上層容器

hdu7108哈希