minitree.cpp

数据结构中最小生成树的C语言实现源代码

// MiniTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"

#define N 6
#define M 10
typedef struct tagVEX 
{
   int data;
   int jihe;
}VEX;
typedef struct tagEDGE
{
   int vexh,vext;
   int weight;
   int flag;
}EDGE;

int main(int argc, char* argv[])
{
	VEX t[N+1];
	EDGE e[M];
    int i,j,k,min,tm_jihe;

    for(i=1;i<=N;i++)
	{
		t[i].data = i;
		t[i].jihe = i;
	}
    
    e[0].vexh = 1;e[0].vext = 2;e[0].weight = 6;e[0].flag = 0;
	e[1].vexh = 1;e[1].vext = 3;e[1].weight = 1;e[1].flag = 0;
	e[2].vexh = 1;e[2].vext = 4;e[2].weight = 5;e[2].flag = 0;
	e[3].vexh = 2;e[3].vext = 3;e[3].weight = 5;e[3].flag = 0;
	e[4].vexh = 2;e[4].vext = 5;e[4].weight = 3;e[4].flag = 0;
    
	e[5].vexh = 3;e[5].vext = 4;e[5].weight = 5;e[5].flag = 0;
	e[6].vexh = 3;e[6].vext = 5;e[6].weight = 6;e[6].flag = 0;
	e[7].vexh = 3;e[7].vext = 6;e[7].weight = 4;e[7].flag = 0;
	e[8].vexh = 4;e[8].vext = 6;e[8].weight = 2;e[8].flag = 0;
	e[9].vexh = 5;e[9].vext = 6;e[9].weight = 6;e[9].flag = 0;
	
	i=1;
	while(i<N)
	{
		min = 100;
		for(j=0;j<M;j++)
		{
			if(e[j].weight<min && e[j].flag==0)
			{
				min = e[j].weight;
				k = j;
			}
		}
		if(t[e[k].vexh].jihe != t[e[k].vext].jihe)
		{
			tm_jihe = t[e[k].vext].jihe;
			e[k].flag = 1; 

			for(j=1;j<=N;j++)
			{
                if(t[j].jihe == tm_jihe)
				{
					t[j].jihe = t[e[k].vexh].jihe;
				}
			}
			i++;
		}
		else
		{
			e[k].flag = 2;
		}
	}
    for(i=0;i<M;i++)
       if(e[i].flag==1)
	 printf("%d,%d :%d\n",e[i].vexh,e[i].vext,e[i].weight);
	return 0;
}