ADJACENCY LIST REPRESENTATION OF A GRAPH AND BREADTH FIRST TRAVERSAL(BFS)

ADJACENCY LIST REPRESENTATION OF A GRAPH AND BREADTH FIRST TRAVERSAL(BFS) USING TEMPLATES

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

A program to create a Graph. The graph is represented using

Adjacency List and traversing the graph in Breadth First Search

Order.

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

#include<iostream.h>

#include <conio.h>

#include <stdlib.h>

#define     MAX      10

#define TRUE 1

#define FALSE 0

template <class T>

class Lgraph

{

private:

typedef struct Gnode

{

T vertex;

struct Gnode *next;

}node;

node *head[MAX];

int visited[MAX];

T Queue[MAX];

int front,rear;

public:

void init();

void create();

void bfs(T);

};

template <class T>

void Lgraph<T>::init()

{

int V1;

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

visited[V1] = FALSE;

front = rear = -1;

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

head[V1] = NULL;

}

/*

--------------------------------------------------------------------------

The create function

It creates the graph using adjacency list

It is called By main

--------------------------------------------------------------------------

*/

template <class T>

void Lgraph<T>::create()

{

T V1, V2;

char ans='y';

node *New,*first;

cout<<"\n\nEnter the vertices no. beginning with 0";

do

{

cout<<"\nEnter the Edge of a graph \n";

cin>>V1>>V2;

// creating link from V1 to V2

New = new node;

if ( New == NULL )

cout<<"Insufficient Memory\n";

New -> vertex = V2;

New -> next = NULL;

first = head[V1];

if ( first == NULL )

head[V1] = New;

else

{

while ( first -> next != NULL )

first = first-> next;

first -> next = New;

}

// creating link from V2 to V1

New = new node;

if ( New == NULL )

cout<<"Insufficient Memory\n";

New -> vertex = V1;

New -> next = NULL;

first = head[V2];

if ( first == NULL )

head[V2] = New;

else

{

while ( first -> next != NULL )

first = first-> next;

first -> next = New;

}

cout<<"\nWant to add more edges?(y/n)";

ans=getche();

}while(ans=='y');

}

/*

--------------------------------------------------------------------------

The bfs Function

It displays the graph in breadth first search manner

Input:Any vertex V1

It is called by main

--------------------------------------------------------------------------

*/

template <class T>

void Lgraph<T>::bfs(T V1)

{

T i;

node *first;

Queue[++rear] = V1;

while ( front != rear)

{

i = Queue[++front];

if ( visited[i] == FALSE )

{

cout<<endl<<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

--------------------------------------------------------------------------

*/

void main ( )

{

// Local declarations

char ans;

Lgraph <int> gr;

int V1;

gr.init();

gr.create();

clrscr();

cout<<"Enter the Vertex from which you want to traverse :";

cin>>V1;

cout<<"The Breadth First Search of the Graph is \n";

gr.bfs(V1);

getch();

}

If you have any query regarding the code,please notify me so that i can help you at my best.Good day.