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

Share on FacebookTweet about this on TwitterDigg thisPin on PinterestShare on LinkedInShare on StumbleUponShare on TumblrShare on Google+Email this to someone

/* 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

Share on FacebookTweet about this on TwitterDigg thisPin on PinterestShare on LinkedInShare on StumbleUponShare on TumblrShare on Google+Email this to someone

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

  1. 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″

    Reply
  2. Nishanthi

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

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

    Reply
  4. Sunanda

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

    Reply
  5. dhanalakshmi

    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.

    Reply
  6. Johnny B

    I think there’s one line missing maybe

    maybe pop that starting vertex into the queue before you hit the while loop?

    Reply
  7. Hossam Fadeel

    Thanks a lot

    Did you try it in Parallel using OpenMP or other Parallel Programming?!!

    Reply
  8. salam
    mishe baraye neveshtane tashkhis derakhte poosha ba zabane c rahnamaim konid merc

    Reply
  9. Mritunjay Pandey

    the code is wrong… it is showing wrong output for some of the inputs like:

    no of vertices: 4
    no of edges: 3

    edges:
    1 3
    3 2
    6 2

    initial vertex: 3

    and the output should be: 3 1 2 6
    and the output of your program is: 3 2 0 0

    Reply
  10. sudarshan

    code is wrong it dos not work properly
    i agree with mrityunjay

    Reply
  11. there showing only one error at the fourth as declaration syntax can you explain it y?

    Reply

Leave a Reply