guangdu.c

广度优先算法 很全的 希望你会喜欢

/////////////////////////////////////////////////////////////////

//图的广度优先搜索法
#include "stdio.h"
#include "stdlib.h"

#define MAXQUEUE 10

struct node
{
	int vertex;
	struct node *nextnode;
};
typedef struct node *graph;
struct node head[9];
int visited[9];

int queue[MAXQUEUE];
int front =-1;
int rear =-1;

//创建图

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*2];
		to =node[i*2+1];

		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;
	}

}

//=========================================================

//队列数据的存入
int enqueue(int value)
{
	if(rear >=MAXQUEUE)
		return -1;
	rear++;
	queue[rear]=value;
}


//==========================================================

//队列数据的取出
int  dequeue()
{
	if(front==rear)
		return -1;
	front++;
	return queue[front];
}

//=========================================================

//图的广度优先搜索法
void bfs(int current)
{
	graph ptr;

	enqueue(current);
	visited[current]=1;
	printf("顶点[%d] ",current);
	while( front !=rear)
	{
		current =dequeue();
		ptr=head[current].nextnode ;
		while(ptr !=NULL)
		{
			if(visited[ptr->vertex ]==0)
			{
				enqueue(ptr->vertex );
				visited[ptr->vertex ]=1;
				//输出遍历顶点
				printf("顶点[%d] ",ptr->vertex );
			}
			ptr=ptr->nextnode ;
		}
	}
}


//=====================================================

//主程序

void main()
{
	graph ptr;

	int node[20][2]={	{1,2},{2,1},
						{1,3},{3,1},
						{2,4},{4,2},
						{2,5},{5,2},
						{3,6},{6,3},
						{3,7},{7,3},
						{4,8},{8,4},
						{5,8},{8,5},
						{6,8},{8,6},
						{7,8},{8,7}
					};
	int i;

	for(i=1;i<=8;i++)
	{
		head[i].vertex =i;
		head[i].nextnode =NULL;
		visited[i]=0;
	}
	Creategraph(node,20);

	printf("图的邻接表的内容:\n");
	for(i=1;i<=8;i++)
	{
		printf("顶点%d=>",head[i].vertex );
		ptr=head[i].nextnode ;
		while(ptr !=NULL)
		{
			printf(" %d ",ptr->vertex );
			ptr=ptr->nextnode ;
		}
		printf("\n");
	}
	printf("图的广度优先搜索内容:\n");
	bfs(1);
	printf("\n");

}