/*********************************************************************************
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 Depth 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]; /*Array Of head nodes/
int visited[MAX]; /visited array for checking whether the array is visited or not/
/*
The error function-declares the error message
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. List
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 Dfs function
Input :Pointer to a vertex of a graph
Output: Displays data in Depth First Search order
Parameter Passing Method : By Value
Called By : main()
Calls : Dfs() itself
*/
void Dfs(int V1)
{
int V2;
node *first;
printf("%d\n", V1);
visited[V1] = TRUE;
first = head[V1];
while ( first != NULL )
if ( visited[first->vertex] == FALSE )
Dfs(first->vertex);
else
first = first -> next;
}
/*
The main function
Input :None
Output:None
Parameter Passing Method :None
Called By : The O.S.
Calls : create(), Dfs()
*/
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 Depth First Search of the Graph is \n");
Dfs(V1);
getch();
}
while(1);
exit(0);
}
/**************** End of the Program *********************/