electrofriends.com > 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 of Ranjith

Author Name :
Ranjith

Total : 16 Comments

Simillar Posts

16 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.

  9. Jane says:
    August 2, 2012 at 4:26 pm

    can you explain each code?? Thanks.

  10. srinu says:
    August 6, 2012 at 1:05 pm

    nice

  11. Johnny B says:
    August 18, 2012 at 11:58 am

    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:
    September 1, 2012 at 6:43 pm

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

  13. Hossam Fadeel says:
    December 22, 2012 at 12:10 am

    Thanks a lot

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

  14. f says:
    January 6, 2013 at 11:24 pm

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

  15. Mritunjay Pandey says:
    March 1, 2013 at 11:45 am

    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:
    May 8, 2013 at 12:24 pm

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

Leave a Reply

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

Free email signup

Email: