Kruskal算法求圖的最小生成樹的完整C代碼是什么

這篇文章給大家介紹Kruskal算法求圖的最小生成樹的完整C代碼是什么，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

算法基本思想

       求加權連通圖的最小生成樹的算法。kruskal算法總共選擇n- 1條邊，所使用的貪婪準則是：從剩下的邊中選擇一條不會產生環(huán)路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環(huán)路則不可能形成一棵生成樹。kruskal算法分e 步，其中e 是網絡中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。

代碼采用鄰接矩陣表示圖，采用邊集表示法，代碼將大大簡化。代碼中很多地方可以優(yōu)化，因為只是用來學習算法，沒有去優(yōu)化。

完整C代碼

/* 最小生成樹的Kruskal算法 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MaxSize 20

typedef char VertexType;

typedef struct Graph {		//定義圖的鄰接矩陣表示法結構
	VertexType ver[MaxSize+1];
	int edg[MaxSize][MaxSize];
}Graph;

typedef struct gEdge {		//定義一個邊集結構，用來存儲圖的所有邊信息
	int begin;
	int end;
	int weight;
}gEdge;

void CreateGraph( Graph *g )		//鄰接矩陣法圖的生成函數
{
	int i = 0;
	int j = 0;
	int VertexNum;
	VertexType Ver;

	printf("請輸入圖的頂點:\n");
	while( '\n' != (Ver=getchar()) ) {
		g->ver[i++] = Ver;
	}
	g->ver[i] = '\0';

	VertexNum = strlen(g->ver);
	printf("請輸入相應的的鄰接矩陣:\n");
	for( i=0; i<VertexNum; i++ )
		for( j=0; j<VertexNum; j++ ) 
			scanf("%d", &g->edg[i][j]);
}

void PrintGraph( Graph g )		//打印圖的結點標識符和鄰接矩陣
{
	int i, j;
	int VertexNum = strlen(g.ver);
	printf("圖的頂點為:\n");
	for( i=0; i<VertexNum; i++ )
		printf("%c ", g.ver[i]);
	printf("\n");

	printf("圖的鄰接矩陣為:\n");
	for( i=0; i<VertexNum; i++ ) {
		for( j=0; j<VertexNum; j++ )
			printf("%d ", g.edg[i][j]);
		printf("\n");
	}
}

int CalVerNum( Graph g )		//求圖的頂點數
{
	return strlen(g.ver);
}

int CalEdgNum( Graph g )		//獲取圖的邊數
{
	Graph p = g;
	int count = 0;
	int VertexNum = CalVerNum( p );
	for( int i=0; i<VertexNum; i++ )
		for( int j=i; j<VertexNum; j++ )		//鄰接矩陣對稱，計算上三角元素和即可
			if( 0 != p.edg[i][j] )
				count++;
	return count;
}

gEdge *CreateEdges( Graph g )					//生成圖的排序過的邊集數組
{
	int i, j;
	int k = 0;
	int EdgNum = CalEdgNum( g );
	int VertexNum = CalVerNum( g );
	gEdge temp;
	gEdge *p = (gEdge *)malloc(sizeof(gEdge)*EdgNum);	

	for( i=0; i<VertexNum; i++ )				//邊集數組初始化,同樣只考慮上三角矩陣
		for( j=i; j<VertexNum; j++ )
			if( 0 != g.edg[i][j] ) {
				p[k].begin = i;
				p[k].end = j;
				p[k].weight = g.edg[i][j];
				k++;
			}
	
	for( i=0; i<EdgNum-1; i++ )		        	//對邊集數組進行選擇排序
		for( j=i+1; j<EdgNum; j++ )
			if( p[i].weight > p[j].weight ) {
				temp = p[i];
				p[i] = p[j];
				p[j] = temp;
			}

	return p;
}

//Kruskal算法生成MST
void Kruskal( Graph g )
{
	int VertexNum = CalVerNum( g );
	int EdgNum = CalEdgNum( g );
	gEdge *p = CreateEdges( g );
	int *index = (int *)malloc(sizeof(int)*VertexNum);		    //index數組，其元素為連通分量的編號，index[i] = index[j] 表示編號為i 和 j的頂點在同一個連通分量中，反之則不在同一個連通分量
	int *MSTEdge = (int *)malloc(sizeof(int)*VertexNum-1);		//MSTEdge數組，用來存儲已確定的MST的邊的編號，共VertexNum-1條邊
	int k= 0;
	int WeightSum = 0;
	int IndexBegin, IndexEnd;

	for(int i=0; i<VertexNum; i++ )		//初始化所有index = -1
		index[i] = -1;

	for( i=0; i<VertexNum-1; i++ ) {
		for(int j=0; j<EdgNum; j++ ) {
			if( !(index[p[j].begin]>=0 && index[p[j].end]>=0 && index[p[j].begin]==index[p[j].end]) ) {  //找到當前還沒加入到同一個連通分量且權值最下的邊
				MSTEdge[i] = j;		//將其加入到MST中去

				if( (-1 == index[p[j].begin]) && (-1 == index[p[j].end]) )			//該邊的兩個頂點都沒加入過任何一個連通分量
					index[p[j].begin] = index[p[j].end] = i;	

				else if( (-1 == index[p[j].begin]) && (index[p[j].end] >= 0) ) {	//該邊的尾end已在一個連通分量，頭begin未加入過任何連通分量
					index[p[j].begin] = i;
					IndexEnd = index[p[j].end];
					for(int n=0; n<VertexNum; n++ )
						if( index[n] == IndexEnd )
							index[n] = i;
				}

				else if( (-1 == index[p[j].end]) && (index[p[j].begin] >= 0) ) {	//該邊的頭begin已在一個連通分量，尾end未加入過任何連通分量
					index[p[j].end] = i;
					IndexBegin = index[p[j].begin];
					for(int n=0; n<VertexNum; n++ )
						if( index[n] == IndexBegin )
							index[n] = i;
				}

				else {
					IndexEnd = index[p[j].end];
					IndexBegin = index[p[j].begin];
					for(int n=0; n<VertexNum; n++ )								//該邊的兩個頂點都已經存在于兩個不同的連通分量中
						if( index[n] == IndexBegin || index[n] == IndexEnd )
							index[n] = i;										//將該連通分量編號全部修改為相同的值
				}
				break;
			}
		}
	}

	printf("MST的邊為:\n");				//輸出MST的邊
	for( i=0; i<VertexNum-1; i++ ) {
		printf("%c--%c\n", g.ver [p[MSTEdge[i]].begin] , g.ver [p[MSTEdge[i]].end] );
		WeightSum+=p[MSTEdge[i]].weight;
	}
	printf("MST的權值為:%d\n", WeightSum);		//輸出MST的權值
}

int main()
{
	Graph g;
	CreateGraph( &g );

	PrintGraph( g );

	Kruskal( g );

	return 0;
}

測試數據和結果

測試的圖為：

測試通過

關于Kruskal算法求圖的最小生成樹的完整C代碼是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。