邻接链表BFS广度优先搜索C语言

广度优先搜索不同于深度优先搜索，广度优先搜索

先搜索当前定点的度，并生成，广度优先搜索树，

他的一个重要性质是可以，计算源节点到其他节点

的最短路径，是许多重要算法的原型，如单源最短

路径或是最小生成树算法。

C代码

void bfs(listpoint g,int s)
{
      int road[9],value[9];
	  listpoint m;
	  queuepoint q;
	  degreepoint n;
	  q = initqueue(q);
	  memset(road,0,sizeof(road));
	  memset(value,0,sizeof(value));
	  road[s] = 1;
	  m = g+s;
	  while(m  != NULL)
	       {
	       	   
	       	     printf("%d(%d) ",m->post,value[m->post]);
	       	     n = m->next.next;
	       	     
	       	     while(n != NULL)
	       	     {
	       	     	  if(road[n->post] == 0)
	       	     	      {
	       	     	      	   road[n->post ] = 1;
	       	     	      	   enqueue(q,g+n->post);
	       	     	      	   value[n->post] = value[m->post]+1;
							  }
							  n = n->next ;
					}
					 m = dequeue(q);
		   }
	  
	  

bfs的实现依赖于使用一个队列来指导优先搜索的

顺序。

完整代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<memory.h> 
#define elemtype int 
#define ok 1
#define fail 0
#define status int 

int value[9];
typedef struct node{
	int post;
	struct node *next;
}degree,*degreepoint;

typedef struct graphnode{        //临街链表 
	elemtype gdata;
	int post;
	degree next;
}graph_list,*listpoint;

typedef struct{               //邻接链表队列 
	listpoint g;
}queue,*queuepoint;

void enqueue(queuepoint q,listpoint g)     //入队 
{
	int i;
	queuepoint m;
	m = q;
	for(i = 0;i<9;i++)
	{
		if(m[i].g  == NULL)
		{
		   m[i].g = g;
		   break;
	}
	}
	
}

listpoint dequeue(queuepoint q)           //出队 
        {
        	int i;
        	queuepoint m;
        	listpoint g;
        	m = q;
        	if(m[0].g != NULL)
        	{
        	g = m[0].g ;
        	for(i = 1;i<9;i++)
        	 {
        		m[i-1].g  = m[i].g ;
              if(i == 9)
               m[i].g = NULL;
          }
			
			return g;
		}
		else
		return NULL;
		}

queuepoint initqueue(queuepoint q)            //初始化队列 
{
	int i;
	q = (queue *)malloc(9*sizeof(queue));
	for(i = 0;i<9;i++)
	{
		q[i].g  = NULL;
	}
	return q;
}

void bfs(listpoint g,int s)
{
      int road[9],value[9];
	  listpoint m;
	  queuepoint q;
	  degreepoint n;
	  q = initqueue(q);
	  memset(road,0,sizeof(road));
	  memset(value,0,sizeof(value));
	  road[s] = 1;
	  m = g+s;
	  while(m  != NULL)
	       {
	       	   
	       	     printf("%d(%d) ",m->post,value[m->post]);
	       	     n = m->next.next;
	       	     
	       	     while(n != NULL)
	       	     {
	       	     	  if(road[n->post] == 0)
	       	     	      {
	       	     	      	   road[n->post ] = 1;
	       	     	      	   enqueue(q,g+n->post);
	       	     	      	   value[n->post] = value[m->post]+1;
							  }
							  n = n->next ;
					}
					 m = dequeue(q);
		   }
	  
	  
	
}

status initlist(graph_list g[])    //创建邻接链表 
{
	int i,m;
	listpoint n;
	degreepoint d;
	for(i = 0;i<9;i++)
	{   
	    g[i].post = i;
	    g[i].next.post = i;
	    d = &(g[i].next) ;
	    printf("enter connect %d\n",i);
		while(scanf("%d",&m))
		{      
		       if(m == -1)
		       {
		       	   d->next = NULL;
		       	   break;
			   }
			   d->next = (degree *)malloc(sizeof(degree));
			   d = d->next;
			   d->post  = m;
		}
		
	}
	return ok;
}

void showlist(graph_list g[])     //打印邻接链表 
{
	int i,j;
	degreepoint m;
	printf("\n\n");
	for(i = 0;i < 9;i++)
	{
		m = &(g[i].next);
		while(m->next != NULL)
		{
			printf("%d->",g[m->post].gdata );
			m = m->next;
		}
		printf("%d\n",g[m->post].gdata );
	}
	printf("\n");
}

int main()
{ 
    queuepoint q;
	graph_list g1[9] = {{1},{2},{3},{4},{5},{6},{7},{8},{9}};

	printf("\n邻接链表\n\n");
    initlist(g1);
    showlist(g1);  
    bfs(g1,0);

  
 
	return 0;
}

运行实例 DEV C++