langc_algo_bfs.c

#include <stdio.h>
/*
	refer to
	https://en.wikipedia.org/wiki/Breadth-first_search
*/
#define MAX_VERTEX  30

int visit[MAX_VERTEX]={0};
int map[MAX_VERTEX][MAX_VERTEX]={0};


int qdata[MAX_VERTEX]={0};
int qhead=0;
int qtail=0;
int qsize=0;


int enqueue(int queue[], int data )
{
	if(qsize >=MAX_VERTEX) return -1;
	
	queue[qtail]= data;
	
	if(qtail == (MAX_VERTEX-1)) qtail=0; // working circle queue
	else qtail++;
	
	qsize++;
	return 0;
}


int dequeue(int queue[], int *data)
{
	
	if(qsize <= 0) return -1;	
	
	*data =	queue[qhead];
	
	if(qhead == (MAX_VERTEX-1)) qhead=0; // working circle queue  
	else qhead++;	
	
	qsize--;
	
	return 0;
}

int BFS(int currentVertex , int nVertex )
{
	int i=0;
	int ret=0;
	
	if( (ret = enqueue(qdata,currentVertex)) != 0)
		printf("error-root enqueue vertex=%d i=%d qsize=%d\n",currentVertex,i,qsize);


	while(qsize > 0)
	{
		if((ret = dequeue(qdata,&currentVertex)) != 0)
			printf("error-main dequeue vertex=%d i=%d qsize=%d\n",currentVertex,i,qsize);
		
		printf("%d->",currentVertex);
		visit[currentVertex] = 1;
		
		for(i=0; i<nVertex;i++ )
		{
			if(map[currentVertex][i] == 1 && visit[i]==0  ){
				if( (ret = enqueue(qdata,i)) != 0)
					printf("error! main-enqueue vertex=%d i=%d qsize=%d\n",currentVertex,i,qsize);
									
			}
		}
		
	}

	return 0;
}

int MAP_print(int nvertex )
{
   int i,j;
	
   printf("\nV ");
   
   for(i=0;i<nvertex;i++)		
   { 
   		 if(i==0)
   		 {
   		 	for(j=0;j<nvertex;j++)
     		{	printf(" %d",j);  
      			if(j==(nvertex-1)) printf("\n");
      		}
   		 }	
   		
		printf("%d: ",i);
		
   		for(j=0;j<nvertex;j++)
      		printf("%d ",map[i][j]);
      	
   		printf("\n");
    }	
    
    return 0;
}

int BFS_test()
{
	int nvertex,nedge;
	int vertex,edge;
	int start,end;
 	int i;
   
	scanf("%d",&nvertex);
	scanf("%d",&nedge);
   
	for(i=0;i<nedge;i++)
   	{
   		scanf("%d %d",&vertex,&edge);   
   		map[vertex][edge]=1;
		map[edge][vertex]=1;   // undirection setting 		
   	}
   	
   	scanf("%d",&start);	
   	scanf("%d",&end);
   	
   	printf("nvertex=%d  nedge=%d\nstart=%d    end=%d \n",nvertex,nedge,start,end);
 	MAP_print(nvertex);	
 
 	printf("\n TEST 1st\n");    
 	BFS(start,nvertex);
 	
 	return 0;
}

/*
refer to
http://www.thecrazyprogrammer.com/2014/03/depth-first-search-dfs-traversal-of-a-graph.html

Input: 
8
10
0 1
0 2
1 5
2 5
5 7
0 3
0 4
3 6
4 6
6 7
0
7

*/

int main(void) {	
	BFS_test();	
	return 0;
}