smalltree.c

图的用法

#include<stdlib.h>
#include<stdio.h>
struct edge							//图的顶点结构
{
	int from;						//开始顶点数据
	int to;							//终点顶点数据
	int weight;						//权值
	struct edge *nextedge;			//指下一边指针
};
typedef struct edge *edgelist;      //边的结构新类型
edgelist list = NULL;               //边链表开始指针
int  node [6];                      //顶点数组
/* --------------------------*/
/*    create the edgelist    */
/* --------------------------*/
edgelist createedgelist(edgelist list,int *edges,int num)
{
	edgelist newnode;
	edgelist last;
	int i;
	for( i = 0;i < num;i++)
	{
		/*创建新边类存*/
	    newnode = (edgelist )malloc(sizeof(struct edge));
		newnode->from = edges[3*i];			       //边的起点
		newnode->to = edges[3*i + 1];			   //边的终点
		newnode->weight = edges[3*i + 2];          //创建成本内容
		newnode->nextedge = NULL;                  //设置指针初值 
		if(list == NULL)                           //第一个结点 
		{
			list = newnode;						  //创建链表开始指针
			last = list;						  //保留最后节点指针
		}
		else
		{
			last->nextedge = newnode;			//连接到最后结点
			last = newnode;						//保留最后结点指针
		}
	}
	return list;                                  //返回链表开始指针
}
/* --------------------------*/
/*  create the Uniongroup    */
/* --------------------------*/
void Uniongroup(int from,int to)
{
	int to_root;
	to_root = to;                                                           //从终点顶点找
	while(node[to_root] > 0)
		to_root = node[to_root];
	node[to_root] = from;                                                   //结合两个顶点
}
/* --------------------------*/
/*  create the samegroup    */
/* --------------------------*/

int samegroup(int from,int to)
{
	int from_root;
	int to_root;
	from_root = from;                                                        //从起点顶点找
	while (node[from_root]>0)
		from_root = node[from_root];
	to_root = to;                                                            //从终点顶点找
	while (node[to_root]>0)
		to_root =node[to_root];
	if(from_root == to_root)                                                 //是否同一个集合
		return 1;
	else 
		return 0;
}
/* --------------------------*/
/*  create the minstree    */
/* --------------------------*/
void minstree()
{
	edgelist ptr;
	ptr = list;                                                               //指向链表开始
	while (ptr != NULL)
	{                                                                         //是否存在同一集合
		if(!samegroup(ptr->from,ptr->to))
		{                                                                     //输出最小权值
			printf("from:%dto:%dvalues: %d\n",ptr->from,ptr->to,ptr->weight);
			Uniongroup(ptr->from,ptr->to);                                    //结合成同一集合
		}
		ptr = ptr->nextedge;                                                  //下一边
	}
}
/* --------------------------*/
/*      the main fuction       */
/* --------------------------*/
void main()
{
		int edges[8][3] = { {2,5,6},{2,4,3},                                //边权值数组
		                    {1,2,2},{1,4,4},
		                    {3,5,5},{3,4,10},
							{2,3,8},{4,5,15},
};
		int i;
		list = createedgelist(list,edges,8);                                //创建边链表
		for(i = 1;i <= 5;i++)                                               //初始顶点数组
			node[i] = -1;
		printf("tu de zui ciao sheng cheng shu:\n");
		minstree();                                                        //创建最小生成数
		printf("\n");
}