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

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

算法基本思想

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

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

完整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代碼是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。