C++ programs to implement Graph Traversal Techniques – Depth First Search/Breadth First Search

a)Program to implement Breadth first Search algorithm.

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,queue[10],front,rear,v,visit[10],visited[10];
void main()
{
	int m;
	clrscr();
	cout <<"enterno of vertices";
	cin >> n;
	cout <<"ente no of edges";
	cin >> m;
	cout <<"\nEDGES \n";
	for(k=1;k<=m;k++)
	{
		cin >>i>>j;
		cost[i][j]=1;
	}
	cout <<"enter initial vertex";
	cin >>v;
	cout <<"Visitied vertices\n";
	cout << v;
	visited[v]=1;
	k=1;
	while(k<n)
	{
		for(j=1;j<=n;j++)
			if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
			{
				visit[j]=1;
				queue[rear++]=j;
			}
		v=queue[front++];
		cout<<v << " ";
		k++;
		visit[v]=0;
		visited[v]=1;
	}
	getch();
}

b)Program to implement Depth First Search Algorithm.

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,stack[10],top,v,visit[10],visited[10];
void main()
{
	int m;
	cout <<"enterno of vertices";
	cin >> n;
	cout <<"ente no of edges";
	cin >> m;
	cout <<"\nEDGES \n";
	for(k=1;k<=m;k++)
	{
		cin >>i>>j;
		cost[i][j]=1;
	}
	cout <<"enter initial vertex";
	cin >>v;
	cout <<"ORDER OF VISITED VERTICES";
	cout << v <<" ";
	visited[v]=1;
	k=1;
	while(k<n)
	{
		for(j=n;j>=1;j--)
			if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
			{
				visit[j]=1;
				stack [top]=j;
				top++;
			}
		v= stack [--top];
		cout<<v << " ";
		k++;
		visit[v]=0; visited[v]=1;
	}
	getch();
}

6 Responses to “C++ programs to implement Graph Traversal Techniques – Depth First Search/Breadth First Search”

  1. Abinaya

    how to do program for depth first search and breadth first search in the same program using stack

    Reply
  2. nishanth roy

    what will be the c++ program for ASAP(as soon as possible) and ALAP(as late as possible) scheduling algorithm..please help me for this

    Reply
  3. Mohamed Rasvi

    The order of the traversal is not depth first traversal. Please rework the program and display the correct order.

    Reply

Leave a Reply