Program to show breadth first search in graph.

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

/*Program: To show operations in graph*/

/*Purpose: Program to show breadth first search in graph*/

/*Date : 05-01-2005*/

/*Time : 12:40*/

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

#include

#include

#define SIZE 10

#define FALSE 0

#define TRUE 1

typedef int adj_mat[SIZE][SIZE];

int front=1,rear=1;

int q[SIZE];

typedef struct graph_t{

int nodes;

int *visited;

adj_mat mat;

}graph;

/**************Function Declaration Begin**********/

void BFS(graph *);

void add_queue(int[],int);

int delete_queue();

/**************Function Declaration End**********/

void main()

{

graph G;

clrscr();

printf(“\n\t\t Program shows Breath First Search in a graph”);

printf(“\n\t\t Enter number of nodes in the graph:”);

scanf(“%d”,&G.nodes);

BFS(&G);

getch();

}

/********** breadth first searching **********/

/********** Function Definition begins **********/

void BFS( graph *G )

{

int k,i,j;

for(k=1;k<=G->nodes;k++)

G->visited[k] = FALSE;

for(i=1;i<=G->nodes;i++)

{

for(j=1;j<=G->nodes;j++)

{

printf(“\n Enter data of vertex %d for(%d,%d):”,i,i,j);

printf(“\n Enter 1 for adjacent vertex and 0 otehrwise”);

scanf(“%d”,&G->mat[i][j]);

}

}

for(k=1;k<=G->nodes;k++)

{

if ( !G->visited[k] )

{

add_queue(q,k);

do

{

k= delete_queue(q);

G->visited[k] = TRUE;

for(j=1;j<=G->nodes;j++)

{

if(G->mat[k][j] == 0)

continue;

if (!G->visited[j])

{

G->visited[j] = TRUE;

add_queue(q, j);

}

}

}while(front!=rear);

}

}

printf(“\n Adjacency matrix of a graph is:\n”);

for(i=1;i<=G->nodes;i++)

{

for(k=1;k<=G->nodes;k++)

{

printf(“%d\t”,G->mat[i][k]);

}

printf(“\n”);

}

i=0;

printf(“\n Traversal of a given graph is\n”);

while(inodes)

{

printf(“%d\t”,q[++i]);

}

}

/********** Function Definition ends **********/

/********** inserting element in queue **********/

/********** Function Definition begins **********/

void enqueue(int q[], int k)

{

q[rear] = k;

rear++;

}

/********** Function Definition ends **********/

/********** deleting element from queue **********/

/********** Function Definition begins **********/

int dequeue(int q[])

{

int data;

data = q[front];

front++;

if(front==SIZE)

{

front=1;

rear=1;

}

return(data);

}

/********** Function Definition ends **********/