nettree.c

单片机程序设计基础 随书光盘

//网络的最小生成树算法（利用邻接矩阵）。
//
//              A
//            / | \
//        4 /   |   \ 7
//        /     |     \
//      B      6|       C
//      | \ 9   |   8 / |
//      |   \   |   /   |
//      |     \ | /     |
//     8|       D       |5
//      |     / | \ 3   | 
//      |  5/   |   \   | 
//      | /     |     \ | 
//      E      4|       F 
//       \      |      /
//         \    |    /  
//        2  \  |  / 9
//              G
//
//

#define N  7  //图的顶点数
#define MAX 9999  //一个远大于边长的数
char DOT[N]={'A','B','C','D','E','F','G'};//存放顶点信息的数组
char visited[N];	//存放顶点被访问标志
int  len[N];		//边长数组
char  F[N];		//父节点

//网络的邻接矩阵（MAX表示不相邻）:
int NET[N][N] ={{0,4,7,6,MAX,MAX,MAX},
		{4,0,MAX,9,8,MAX,MAX},
		{7,MAX,0,8,MAX,5,MAX},
		{6,9,8,0,5,3,4},
		{MAX,8,MAX,5,0,MAX,2},
		{MAX,MAX,5,3,MAX,0,9},
		{MAX,MAX,MAX,4,2,9,0}};

void MINTREE ( int k ) //从序号为k的顶点出发构造网络的最小生成树
{
	int i,j,p,min;
	for (i=0;i<N;i++) visited[i]=0;//初始化访问标志
	visited[k] = 1 ; //首先将序号为k的顶点加入最小生成树
	for (i=0;i<N;i++) F[i] = (i==k)?'*':DOT[k] ;	//初始化父节点
	for (i=0;i<N;i++) len[i] = NET[k][i] ;	//初始化边长数组
	for (i=0;i<N-1;i++) {  //将其它N-1个顶点加入到最小生成树中
		min=MAX;p=-1;  //寻找到当前生成树最近的顶点
		for (j=0;j<N;j++) if (!visited[j] && len[j] <min ){
			min = len[j] ; p = j ;
			}
		visited[p] = 1 ; //将该顶点加入最小生成树
		for (j=0;j<N;j++) //调整其它顶点到最小生成树的边长
			if ( !visited[j] && NET[j][p] < len[j] ) {
				len[j]=NET[j][p];//更短的边长
				F[j]=DOT[p];  //新的父节点
				}
		}
}
//求解结果（本网络的最小生成树是唯一的，与根节点的选择无关）：
//              A
//            / |  
//        4 /   |      
//        /     |      
//      B      6|       C
//              |       |
//              |       |
//              |       |
//              D       |5
//              | \ 3   | 
//              |   \   | 
//              |     \ | 
//      E      4|       F 
//       \      |       
//         \    |       
//        2  \  |     
//              G
//
//

main ( )
{
	int  i,j;
	for (i=0;i<N;i++)
		MINTREE (i) ; //从序号为i的顶点出发构造网络的最小生成树
	while (1) ; //在这一行设置断点,中止程序运行,以便观察程序运行的结果 
}