The Program supports both undirected and Directed Graphs and traverse the graph in Breadth First Search Order in C language.

        Program to create a Graph. The graph is represented using

Adjacency List. The Program supports both undirected and

Directed Graphs and traverse the graph in Breadth First Search

Order.


********************************************************************/


/* List of include files */


#include <stdio.h>

#include <conio.h>

#include <process.h>

#include <stdlib.h>


/* List of defined constants */


#define MAX 10

#define TRUE 1

#define FALSE 0


/* Global declarations */

typedef struct node

{

int vertex;

struct node *next;

}node;


/* Declare an adjacency matrix for storing the graph */


node   *head[MAX];

int    visited[MAX];

int    Queue[MAX];

int    front, rear;


/*

The error function

Input : A character string consisting of error message

Output: Prints the error message

Parameter Passing Method : Call By Reference

Called By : create()

Calls : None

*/


void error( char *Msg )

{

printf("%s\n", Msg );

printf("Press any key to abort\n");

getch();

exit(1);

}


/*

The add function

Input : The vertices of an edge

Output: None, modifies Headnode list

Parameter Passing Method : Call By Value

Called By : create()

Calls : None

*/

void add(int Hnode, int vnum)

{

node *New, *first;


New = (node *) malloc(sizeof(node ) );

if ( New == NULL )

error("Insufficient Memory\n");

New -> vertex = vnum;

New -> next = NULL;

first = head[Hnode];

if ( first == NULL )

   head[Hnode] = New;

else

{

while ( first -> next != NULL )

first = first-> next;

first -> next = New;

}

}

/*

The create function

Input :None

Output:None, creates graph and stores in Adj. Lists

Parameter Passing Method :None

Called By : main()

Calls : error(), add()

*/

void  create()

{

int V1, V2;


for ( V1 = 0; V1 < MAX; V1++)

head[V1] = NULL;

do

{

printf("\nEnter the Edge of a graph \n");

scanf("%d%d", &V1, &V2);

if ( V1 == -99)

   break;

if ( V1 >= MAX || V2 >= MAX)

error("Invalid Vertex Value\n" );

else

add(V1, V2);

}

while(1);

}


/*

The bfs function

Input :Pointer to one of the vertex of the graph

Output: Displays data in breadth First Search order

Parameter Passing Method : By Value

Called By : main()

Calls : None

*/

void bfs(int V1)

{

int i;

node *first;


Queue[++rear] = V1;

while ( front != rear)

{

i = Queue[++front];

if ( visited[i] == FALSE )

{

printf("%d\n", i);

visited[i] = TRUE;

}

first = head[i];

while ( first != NULL )

{

if ( visited[first->vertex] == FALSE )

Queue[++rear] = first->vertex;

first = first -> next;

}

}

}


/*

The main function

Input :None

Output:None

Parameter Passing Method :None

Called By : The O.S.

Calls : create(), bfs()

*/

void main ( )

{

/* Local declarations */

int V1, V2;


create();

do

{

for ( V1 = 0; V1 < MAX; V1++)

  visited[V1] = FALSE;

printf("Enter the Vertex from which you want to traverse :");

scanf("%d", &V1);

if ( V1 == -99)

   break;

if ( V1 >= MAX )

error("Invalid Vertex\n");

printf("The Breadth First Search of the Graph is \n");

front = rear = -1;

bfs(V1);

getch();

}

while(1);

exit(0);

}


/**************** End of the Program *********************/

 



Post a Comment

Previous Post Next Post