BFS Graph implemented in C

Breadth First Search Graph

Read below about BFS Graph implementation in C.( Breadth First Search )

Problem : Show minimum cost path from source to destination using BFS at source. Solution in C Language given below:


Implemented (Study Purpose) by :
Zahid Bin Abdur Rouf, 
07-1, Computer Science & Engineering , 
American International University - Bangladesh.
2007


Code in C language:

/**************************************************************
 * Breadth First Search in Graph ( BFS ):                     *
 * Show minimum cost path from source to destination          *
 * using BFS at source .                                      *
 *************************************************************/
#include 
#include 
#include 
#include 

using namespace std ;
#define MAX 100

#define WHITE 0
#define GREY 1
#define BLACK 2
#define EDGE 1 

int i , j , m , n ;

int M , N ;
 
deque Q ;

deque :: iterator p ;

int graph[MAX ][MAX ];
int color[MAX ];
int dist[MAX];
int finish[MAX];

int parent[MAX ] ;

void printPath(int start , int end )
{
 if( start == end )
  printf("%d ",start);

 else if( parent[ end ] == -1 )
  printf("No path from %d to %d\n",start,end);

 else
 {
  printPath( start , parent[end ] );

  printf("-> %d ",end ); 
 }  
}

void Bfs( int s )
{
 int u ;
      /** INITIALIZATION **/
 for(i = 1 ; i <= N ; i++)
 {
  color[ i ] = WHITE ;

  dist[i ]   = -1 ;
  parent[ i] = -1 ;
 }
 color[ s ] = GREY ;

 dist[s ] = 0 ;   /**INITIALIZE DISTANCE OF SOURCE TO ZERO**/

 parent[s ] = -1 ;

 Q.push_back(s) ;  

 while( !Q.empty() )       // LOOP UNTIL QUEUE(Q) IS EMPTY 
 {
    u = Q.front();

    Q.pop_front();   /** POP FROM QUEUE **/

    for( i=1 ; i<= N; i++)
    {  
  if( color[i ] == WHITE && graph[u][i] == 1 )
  {
   color[i ] = GREY ;
 
     dist[i ] = dist[u] + 1 ;
    
   parent[ i] = u ;
      
   Q.push_back( i ); /** PUSH INTO QUEUE **/
  }
    }
    color[u ] = BLACK ;
 }
}








int main(void)
{
// freopen("t.in","r",stdin);
// freopen("t.out","w",stdout);
 
 int a, b ;

 scanf("%d",&N);         /**Verticess (N) ******/

while( 1 )         /** INPUT EDGES ****/
 {
  scanf("%d %d",&a,&b);

  if( a== 0 && b==0 )
   break ;

  graph[a][b] = 1 ;  
 }
 while( scanf("%d",&a) != EOF )       /* ENTER START AND END */
 {
  scanf("%d",&b);
           Bfs(a);    /** EXPLORE ALL NODE FROM START TO END **/
       /** BFS() CALLING WITH STARTING NODE **/

  printf(" Source: %d , Destination: %d\t",a,b);

  printPath(a,b);      /** printPath() CALL **/

  printf(" End of Path\n\n");
 }
 return 0 ;
}


// END OF CODE

INPUT:
---------

8
1 2
1 4
2 1
2 3
3 2
4 1
4 5
4 8
5 4
5 6
5 8
6 5
6 7
7 6
7 8
8 4
8 5
8 7
0 0
1 7
3 7
4 6

Sample Output:
--------------

 Source: 1 , Destination: 7, 1 -> 4 -> 8 -> 7  End of Path

 Source: 3 , Destination: 7, 3 -> 2 -> 1 -> 4 -> 8 -> 7  End of Path

 Source: 4 , Destination: 6, 4 -> 5 -> 6  End of Path

Time complexity of BFS Algorithm:

Worst Case: Big O of ( V + E ) , where V is Vertex,E is Edge