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 *********************/