C++ programs for the implementation of Breadth First Search(BFS) for a given graph

Thursday, March 11th, 2010

/* Write C++ programs for the implementation of BFS for a given graph */

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];
 
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 <<"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;
qu[rare++]=j;
}
v=qu[front++];
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}

OUTPUT
enterno of vertices9
ente no of edges9

EDGES
1 2
2 3
1 5
1 4
4 7
7 8
8 9
2 6
5 7
enter initial vertex1
Visited vertices
12 4 5 3 6 7 8 9

Avatar Image

Author Name :
Ranjith

Total : 4 Comments


4 Responses to C++ programs for the implementation of Breadth First Search(BFS) for a given graph

  1. Alex

    I guess, that there must be a space between 1 and 2 in “Visited vertices
    1(here should be a space?)2 4 5 3 6 7 8 9″

  2. Nishanthi

    thanks for your simple way of implementing the program
    can you plz help me in implementing DFS in c

  3. dfs

    implementation

  4. Ashwin

    Nic one! But how do we implement by linked list ?

Leave a Reply

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup