Logo 
Search:

C Programming Articles

Submit Article
Home » Articles » C Programming » Data File StructureRSS Feeds

Program that implements breadth first search algorithm

Posted By: Madison Campbell     Category: C Programming     Views: 10298

Program that implements breadth first search algorithm.

Code for Program that implements breadth first search algorithm in C Programming

#include <stdio.h>
#include <conio.h>
#include <alloc.h>

#define TRUE 1
#define FALSE 0
#define MAX 8

struct node
{
    int data ;
    struct node *next ;
} ;

int visited[MAX] ;
int q[8] ;
int front, rear ;

void bfs ( int, struct node ** ) ;
struct node * getnode_write ( int ) ;
void addqueue ( int ) ;
int deletequeue( ) ;
int isempty( ) ;
void del ( struct node * ) ;

void main( )
{
    struct node *arr[MAX] ;
    struct node *v1, *v2, *v3, *v4 ;
    int i ;

    clrscr( ) ;

    v1 = getnode_write ( 2 ) ;
    arr[0] = v1 ;
    v1 -> next = v2 = getnode_write ( 3 ) ;
    v2 -> next = NULL ;

    v1 = getnode_write ( 1 ) ;
    arr[1] = v1 ;
    v1 -> next = v2 = getnode_write ( 4 ) ;
    v2 -> next = v3 = getnode_write ( 5 ) ;
    v3 -> next = NULL ;

    v1 = getnode_write ( 1 ) ;
    arr[2] = v1 ;
    v1 -> next = v2 = getnode_write ( 6 ) ;
    v2 -> next = v3 = getnode_write ( 7 ) ;
    v3 -> next = NULL ;

    v1 = getnode_write ( 2 ) ;
    arr[3] = v1 ;
    v1 -> next = v2 = getnode_write ( 8 ) ;
    v2 -> next = NULL ;

    v1 = getnode_write ( 2 ) ;
    arr[4] = v1 ;
    v1 -> next = v2 = getnode_write ( 8 ) ;
    v2 -> next = NULL ;

    v1 = getnode_write ( 3 ) ;
    arr[5] = v1 ;
    v1 -> next = v2 = getnode_write ( 8 ) ;
    v2 -> next = NULL ;

    v1 = getnode_write ( 3 ) ;
    arr[6] = v1 ;
    v1 -> next = v2 = getnode_write ( 8 ) ;
    v2 -> next = NULL ;

    v1 = getnode_write ( 4 ) ;
    arr[7] = v1 ;
    v1 -> next = v2 = getnode_write ( 5 ) ;
    v2 -> next = v3 = getnode_write ( 6 ) ;
    v3 -> next = v4 = getnode_write ( 7 ) ;
    v4 -> next = NULL ;

    front = rear = -1 ;
    bfs ( 1, arr ) ;

    for ( i = 0 ; i < MAX ; i++ )
        del ( arr[i] ) ;

    getch( ) ;
}

void bfs ( int v, struct node **p )
{
    struct node *u ;

    visited[v - 1] = TRUE ;
    printf ( "%d\t", v ) ;
    addqueue ( v ) ;

    while ( isempty( ) == FALSE )
    {
        v = deletequeue( ) ;
        u = * ( p + v - 1 ) ;

        while ( u != NULL )
        {
            if ( visited [ u -> data - 1 ] == FALSE )
            {
                addqueue ( u -> data ) ;
                visited [ u -> data - 1 ] = TRUE ;
                printf ( "%d\t", u -> data ) ;
            }
            u = u -> next ;
        }
    }
}

struct node * getnode_write ( int val )
{
    struct node *newnode ;
    newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
    newnode -> data = val ;
    return newnode ;
}

void addqueue ( int vertex )
{
    if ( rear == MAX - 1 )
    {
        printf ( "\nQueue Overflow." ) ;
        exit( ) ;
    }

    rear++ ;
    q[rear] = vertex ;

    if ( front == -1 )
        front = 0 ;
}

int deletequeue( )
{
    int data ;

    if ( front == -1 )
    {
        printf ( "\nQueue Underflow." ) ;
        exit( ) ;
    }

    data = q[front] ;

    if ( front == rear )
        front = rear = -1 ;
    else
        front++ ;

    return data ;
}

int isempty( )
{
    if ( front == -1 )
        return TRUE ;
    return FALSE ;
}

void del ( struct node *n )
{
    struct node *temp ;

    while ( n != NULL )
    {
        temp = n -> next ;
        free ( n ) ;
        n = temp ;
    }
}
  
Share: 


Didn't find what you were looking for? Find more on Program that implements breadth first search algorithm Or get search suggestion and latest updates.

Madison Campbell
Madison Campbell author of Program that implements breadth first search algorithm is from Toronto, Canada.
 
View All Articles

Related Articles and Code:


 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
Asif Raza from United States Comment on: Oct 08
oh.. long code.. Though nice work. as a programmer, here is the code for same algorithm, please have a look at it.. its small in length and easier to understand as well as implement
in.docsity.com/.../Breadth-first_Search_Algorithm_-_C_plus_plus_Code

View All Comments