bfs.c

图的用法

#include<stdlib.h>
#include<stdio.h>
#define SIZE 100
#define MAXyjj_queue  10            //队列的最大容量
struct node               //图的顶点结构
{
	int vertex;           //顶点数据
	struct node *nextnode;
};
typedef struct node *graph;        //图的结构新类型
struct node head[9];               //图顶点结构数组
int yjj_visited[9];                    //遍历记录数组
int yjj_queue[MAXyjj_queue];               //队列的数组声明
int yjj_front = -1;                    //队列的对头
int yjj_rear = -1;                     //队列的对尾
int **yjj_node;                        //保存用户输入的数据的一个数组（起点。终点。权值）
int yjj_cost[SIZE][SIZE];              //保存权值

/* --------------------------*/
/*      create the graph       */
/* --------------------------*/
void creategraph(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];                    //边的权值
		/* 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;                          //插入结尾
	}
}
/* --------------------------*/
/*        duilie data save   */
/* --------------------------*/
int enyjj_queue(int value)                  //向队列里插入数据
{
	if(yjj_rear >= MAXyjj_queue)
	{
		printf("yjj_queue is full of ");
		return -1;
	}
	yjj_rear ++;                            //队尾指针往前移动
	yjj_queue[yjj_rear] = value;                //存入队列
}

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

int deyjj_queue()                           //取出数据
{
	if(yjj_front == yjj_rear)
	{
		printf("yjj_queue is empty ");
		return -1;
	}
	yjj_front ++;                           //队头指针往前移动
	return yjj_queue[yjj_front];                //取出队列
}


/* --------------------------*/
/*        crete the bfs      */
/* --------------------------*/

void bfs(int current)                             //广度遍历
{
	graph ptr;
	/* 处理第一个顶点*/
	enyjj_queue(current);                            //将顶点存入队列
	yjj_visited[current] = 1;                        //记录已经遍历过
	printf("dingdian[%d]   ",current);           //输出遍历顶点值
	while (yjj_front != yjj_rear)
	{   
		current = deyjj_queue();                     //将顶点从队列中取出
		ptr = head[current].nextnode;            //顶点位置
		while(ptr != NULL)
		{
			if(yjj_visited[ptr->vertex] == 0)        //如果没有遍历过
			{		
				enyjj_queue(ptr->vertex);          //递归遍历调用
				yjj_visited[ptr->vertex] = 1;
				printf("dingdian[%d]   ",ptr->vertex);
			}                                
			ptr = ptr ->nextnode;              //下一个顶点
		}
	}

}

/* --------------------------*/
/*      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 <= 8;i++ )
	{
		head[i].vertex = i;                  //设置顶点值
		head[i].nextnode = NULL;             //清楚图指针
	    yjj_visited[i] = 0;                      //设置遍历初值
	}
	creategraph(yjj_node,20);                      //create graph

	printf("bfs:\n");
	bfs(1);
	printf("\n");
}