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

by Nideesh C on April 12, 2011 · 0 comments

in C++




a)Program to implement Breadth first Search algorithm.

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,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();
}

 

#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();
}



Not Satisfied ? Just search & get the result

Related Posts Plugin for WordPress, Blogger...
Be Sociable, Share!

Related posts:

  1. C++ program to implement Stack using Formula Based Representation
  2. Program to implement Binary Search Algorithm
  3. C++ program to implement stack using Linked List
  4. C++ program to implement circular queue using array
  5. C++ program to implement Shell sort using class

Leave a Comment

Previous post:

Next post: