toposort.c

图的用法

/*   拓扑排序的实现，解决一类需要先做什么，再做什么，比如学习一系列基本教程以及施工队进入工地的时间安排顺序！

*/
#include<stdlib.h>
#include<stdio.h>
#define SIZE 100
#define MAXqueue  20      //队列的最大容量
struct node               //图的顶点结构声明
{
	int vertex;                  //顶点数据
	struct node *nextnode;       //指向下一个顶点的指针
};
typedef struct node *graph;      //图的结构新类型
struct node head[SIZE];          //图顶点结构数组
int yjj_queue[MAXqueue];             //队列的数组声明
int yjj_front = -1;					 //队列的队头
int yjj_rear = -1;					 //队列的对尾
int **yjj_node;                      //保存用户输入的数据的一个数组（起点。终点。权值）
int yjj_cost[SIZE][SIZE];            //保存权值，yjj_cost[0][0]里面的没有


/* ----------------------------------*/
/*    create the graph contion du    */
/* ----------------------------------*/


void creategraph(graph head,int **node,int num)
{
	graph newnode;           //新顶点指针
	graph ptr;
	int from;                //边的起点
	int to;                  //边的终点
	int i;

	for(i = 0;i < num;i++)                               //读取边的循环
	{
		from = node[i][0];                               //边的起点
		to = node[i][1];                                 //边的终点
	   	yjj_cost[from][to] = node[i][2];
		head[to].vertex += 1;                            //入度加一
		/* create newnode */
		newnode = (graph )malloc(sizeof(struct node));
		newnode->vertex = to;
		newnode->nextnode = NULL;
		ptr = &(head[from]);
		while(ptr->nextnode != NULL)
			ptr = ptr->nextnode;                          //下一个顶点
		ptr->nextnode = newnode;                          //插入结尾
	}
}


/* ----------------------------------*/
/*        excute the toposort        */
/* ----------------------------------*/
int toposort(graph head,int num)
{
	graph ptr;
	int i;

	/* 将入度为零的顶点存入队列的循环*/
	for( i = 1;i <= num*2;i++)
	{
		ptr = head[i].nextnode;                               
		if(head[i].vertex == 0&&ptr ->nextnode != NULL)   //入度为零
	 		enqueue(i);           //存顶点到队列
		ptr = NULL;
	}
	while((i = dequeue())!= -1)
	{
		printf("%d ",i);            //输出拓扑排序的顶点
		ptr = head[i].nextnode;     //顶点位置
		while(ptr != NULL)
		{
			i = ptr -> vertex;                //得到顶点值
			head[i].vertex --;                //顶点入度减一
			if(head[i].vertex == 0)           //如果入度是0
				enqueue(i);                   //存顶点到队列
	 		ptr = ptr -> nextnode;            //下一个顶点

		}
	}
	printf("\n");
	for( i = 1;i <= num;i++)                 //  检查是否有循环  
	if(head[i].vertex != 0)                  //  入度不是0
		return 1;                            //  有回路
	return 0;                                //  没有回路
}


/* --------------------------*/
/*        duilie data save   */
/* --------------------------*/

int enqueue(int value)                  //向队列里插入数据
{
	if(yjj_rear + 1 == yjj_front || yjj_rear == (MAXqueue - 1)&&yjj_front <= 0)       // 检查队列是否已满
		return -1;                                                    // 无法存入
	yjj_rear ++;                                                          //队尾指针往前移动
	if(yjj_rear == MAXqueue)                                              //是否超过界限
		yjj_rear =  0 ;                                                      //从头开始
	yjj_queue[yjj_rear] = value;                                              //存入队列
}

/* --------------------------*/
/*        duilie data output   */
/* --------------------------*/

int dequeue()                           //取出数据
{
	if(yjj_front == yjj_rear)                                                //检查队列是否为空
	{
		return -1;                                                   //无法取出
	}
	yjj_front ++;                                                        //队头指针往前移动
	if(yjj_front == MAXqueue)                                            //是否超过界限
		yjj_front = 0;                                                   //从头开始
	return yjj_queue[yjj_front];                                             //队列取出
}

/* --------------------------*/
/*      the main fuction     */
/* --------------------------*/
void main()
{
	graph  ptr;
    /*----------------------------------------------------------------*/
	int m,n=3;            //控制动态二维数据的声请
    int i;
	clrscr();
	/* 建立二维数组保存用户的输入：包括（起点，终点，以及权值）*/
	printf("Please input one number:\n");
	scanf("%d",&m);
	yjj_node = (int **) malloc(m*sizeof(int *));
	for(i = 0;i < m;i ++)
		yjj_node[i] = (int *)malloc(n*sizeof(int));
	for(i = 0;i < m;i ++)
		{
			printf("Please input datas:\n");
			scanf ("%d,%d,%d",&yjj_node[i][0],&yjj_node[i][1], &yjj_node[i][2]) ;
		}
    /*----------------------------------------------------------------*/

	for(i =1;i <=SIZE;i++)
	{
		head[i].vertex = 0;                           //设置顶点值
		head[i].nextnode = NULL;                      //清除图的指针
	}
	creategraph( head,yjj_node,m);
    //creategraph( head2,node,10);
	printf("fisrt graph:\n");
	if(toposort( head, m))                            //拓扑排序
		printf("have ciycal:\n");
	else 
		printf("do not have ciycal:\n");
	yjj_front = yjj_rear = -1;                                 //清除队列
}