Home > Source Codes > Software Programs > C++ Programs > Data structure > C++ programs for the implementation of Breadth First Search(BFS) for a given graph

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 : 8 Comments

Simillar Posts

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

  1. Alex says:
    April 7, 2010 at 2:50 pm

    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 says:
    March 15, 2011 at 9:09 am

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

  3. dfs says:
    September 29, 2011 at 3:05 pm

    implementation

  4. Ashwin says:
    October 28, 2011 at 1:09 pm

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

  5. Milon says:
    February 22, 2012 at 7:57 pm

    Thanks 4 the program. Before this example I didn’t understand BFS. But now I have understood it. Thanks again a lot.

  6. user says:
    April 10, 2012 at 3:57 pm

    nice, but doesn’t work try with initial vertex 4 or 7

  7. Sunanda says:
    April 18, 2012 at 1:30 pm

    Impressive.. Short and understandable code… NIce.. keep it up.. and thanx..

  8. dhanalakshmi says:
    May 4, 2012 at 4:46 pm

    will you try this program in this way.
    input is asking the no.of vertices?
    and asking the adjecency matrix?
    then output comes like visited nodes.
    so please try in this way.

Leave a Reply

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

Free email signup