kruskal_gao.cpp

Kruskal算法寻找最小生成树,C语言实现

/************************************************************************/
/*					Kruskal 算法 寻找最小生成树                         */
/*						by gaobin 2005-11-14							*/
/************************************************************************/
#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

#define NODE_NUM	6			// 顶点个数
#define MPV			128			// 最大权值
#define NOT_CONNECTED	0
#define CONNECTED		1
#define YES		1
#define NO		0

typedef int vex_type;
typedef int Adj_type;

typedef struct {
	vex_type start_vex;		// 始点
	vex_type stop_vex;		// 终点
	int weight;		// 权值
} Edge;

typedef struct {
	vex_type vexs[NODE_NUM];
	Adj_type adjs[NODE_NUM][NODE_NUM];
	int nNode;
} GraphMatrix;		// 图的邻接矩阵定义

typedef struct AdjNode{
	Edge adj;
	struct AdjNode *next;
} ADJNODE;

void Kruskal(GraphMatrix *pGraph, Edge mst[], Adj_type linkinfo[][NODE_NUM]);
void CreateEdgeList(ADJNODE *&pList, GraphMatrix *pGraph);
void GetMinAdj(ADJNODE *&pList, Edge &tmpAdj);
int ThereIsNoCircle(Adj_type linkinfo[][NODE_NUM], Edge tmpAdj);
void AddAdjtoMst(Edge mst[], Edge tmpAdj, int &nAdj);
void AdjustLinkInfo(Edge tmpAdj, Adj_type linkinfo[][NODE_NUM]);
void FreeList(ADJNODE *&pList);

int main() {
	GraphMatrix graphmatrix =  {    {0},
									{ 0,	 10,   MPV,  MPV,   19,  21,
									  10,     0,    5,	 6,   MPV,  11,
									  MPV,     5,    0,   6,   MPV,  MPV,
									  MPV,	  6,    6,   0,   18,  14,
									  19,     MPV,  MPV,  18,    0,  33,
									  21,     11,  MPV,  14,   33,  0  },
									  NODE_NUM
								};
	Adj_type linkinfo[NODE_NUM][NODE_NUM] = { NOT_CONNECTED };
	Edge mst[NODE_NUM-1];
	Kruskal(&graphmatrix, mst, linkinfo);
	
	int i;
	printf("startnode\tstopnode\t\tweight\n");
	for ( i = 0; i < NODE_NUM-1; i++ ) {
		printf("%d\t\t%d\t\t\t%d\n", mst[i].start_vex, mst[i].stop_vex, mst[i].weight);
	}

	return 0;
}

void Kruskal(GraphMatrix *pGraph, Edge mst[], Adj_type linkinfo[][NODE_NUM]) {
	ADJNODE *pList;
	CreateEdgeList(pList, pGraph);		// 获得所有边,加入到链表pList中
	int nAdj = 0;
	Edge tmpAdj;
	while ( nAdj < NODE_NUM -1 ) {
		GetMinAdj(pList, tmpAdj);		// 找出当前最小的边
		if ( ThereIsNoCircle(linkinfo, tmpAdj) == YES ) {	// 加入边后无自环
			AddAdjtoMst(mst, tmpAdj, nAdj);		// 将边加入到结果集合中
			AdjustLinkInfo(tmpAdj, linkinfo);	// 调整顶点的连通信息矩阵
		}
	}
	FreeList(pList);	// 释放链表中的其他节点
}

void CreateEdgeList(ADJNODE *&pList, GraphMatrix *pGraph) {
	ADJNODE *pTmp, *pEnd = pList;
	int i, j, first = 1;
	for ( i = 0; i < NODE_NUM; i++ ) {
		for ( j = i+1; j < NODE_NUM; j++ ) {
			if ( pGraph->adjs[i][j] >= 0 && pGraph->adjs[i][j] < MPV ) {
				pTmp = (ADJNODE*)malloc(sizeof(ADJNODE));
				pTmp->adj.start_vex = i;
				pTmp->adj.stop_vex = j;
				pTmp->adj.weight = pGraph->adjs[i][j];
				pTmp->next = NULL;
				if ( first == 1 ) {
					first = 0;
					pList = pTmp; pEnd = pTmp;
				}
				else {
					pEnd->next = pTmp;
					pEnd = pTmp;
				}
			} // if
		}	// for j
	}	// for i
}

void GetMinAdj(ADJNODE *&pList, Edge &tmpAdj) {
	ADJNODE *pCur = pList, *pPre = pList;
	ADJNODE *pDcur, *pDpre;
	int weight = MPV;
	while ( pCur != NULL ) {
		if ( pCur->adj.weight < weight ) {
			pDpre = pPre;
			pDcur = pCur;
			weight = pCur->adj.weight;
		}
		pPre = pCur;
		pCur = pCur->next;
	}
	tmpAdj.start_vex = pDcur->adj.start_vex;
	tmpAdj.stop_vex = pDcur->adj.stop_vex;
	tmpAdj.weight = weight;
	// Delete the minimum node;
	if ( pDcur == pDpre ) {
		pList = pList->next;
	}
	else {
		pDpre->next = pDcur->next;
	}
	free(pDcur);
}

int ThereIsNoCircle(Adj_type linkinfo[][NODE_NUM], Edge tmpAdj) {
	int i = tmpAdj.start_vex;
	int j = tmpAdj.stop_vex;
	if ( linkinfo[i][j] == CONNECTED ) {
		return NO;
	}
	else{
		linkinfo[i][j] = CONNECTED;
		return YES;
	}
}

void AddAdjtoMst(Edge mst[], Edge tmpAdj, int &nAdj) {
	mst[nAdj] = tmpAdj;
	nAdj++;
}

void AdjustLinkInfo(Edge tmpAdj, Adj_type linkinfo[][NODE_NUM]) {
	int i = tmpAdj.start_vex;
	int j = tmpAdj.stop_vex;
	assert(i < j);
	int k;
	for ( k = i+1; k < NODE_NUM; k++ ) {
		if ( linkinfo[i][k] == CONNECTED && k != j ) {	
			// 若找到了始点i连通的其他边,则新加入边的终点j,与该边的终点k也是连通的
			// 更新连通矩阵的信息
			linkinfo[k][j] = CONNECTED;
			linkinfo[j][k] = CONNECTED;
		}
	}
}

void FreeList(ADJNODE *&pList) {
	ADJNODE *pTmp = pList;
	while ( pList != NULL ) {
		pList = pList->next;
		free(pTmp);
		pTmp = pList;
	}
}