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

Author Name :
Ranjith

Total : 19 Comments


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

  1. Alex says:

    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:

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

  3. dfs says:

    implementation

  4. Ashwin says:

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

  5. Milon says:

    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:

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

  7. Sunanda says:

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

  8. dhanalakshmi says:

    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.

  9. Jane says:

    can you explain each code?? Thanks.

  10. srinu says:

    nice

  11. Johnny B says:

    I think there’s one line missing maybe

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

  12. hammad says:

    please give me bfs and dfs with queue from classes
    my mail address is homatts@hotmail.com

  13. Hossam Fadeel says:

    Thanks a lot

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

  14. f says:

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

  15. Mritunjay Pandey says:

    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

  16. sudarshan says:

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

  17. deepu says:

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

  18. tera baap says:

    Gandu code galat ha tera…..yaki ha yaki…….

  19. priyanka & saranya says:

    code is wrong…will not show the correct output…

Leave a Reply

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

Free email signup

Email: