i want to learn bfs & dfs,can someone provide me stl(c++) implementation of bfs?

please provide vector implementation im unable to understand role of map

Ok, I will update that.

Check these links again, I have updated it.

BFS : https://github.com/Shraeyas/General-Codes/blob/master/bfs.cpp
DFS : https://github.com/Shraeyas/General-Codes/blob/master/dfs.cpp

one query-> s = q.front();
q.pop();

it should be
q.pop(); then
q.front();
am i right?

You can surely refer this link:
Data Structures & Algorithms.
You can find everything here i.e Tutorial, Implementation, Problem Set etc. I hope it helped !

1 Like

Yes, you are right! I fixed it. Thanks :slight_smile:

BFS:

  1. push initial state on queue and mark it as visited.

2)while queue is not empty repeat

2.1) pop a state from the queue, lets call this state X

2.2) Iterate all neighbouring states of X which are not visited yet, mark them as visited and push them on the queue.

DFS:

Use the same algorithm but use stack instead of queue :slight_smile:

2 Likes

Bro, Here(Hackerearth) you can find all graphs algorithms and there implementation using STL. Also next to each tutorial,
practice problems are available try to solve them, if you are unable to solve look at editorials and solve it again or take help from other user solution.

Link

1 Like

vector adj[10]; it same like vector<vector> adj(10)… ?

code is not working fine for input
5 3
1 2
1 3
2 4
it gives output 2 3 1 4

what is wrong in this code http://ideone.com/1uOMcF

code link-http://ideone.com/1uOMcF

vectoradj[10] means we are taking an array of vectors and vector<vector >adj(10) means we are taking a vector of vector and we have already put 10 elements in the vector to initialise it.

Yes, both will do same work.

In first vector adj[10] :
we are making array of vector(vector containing integer) therefore,
adj[0] -> vector
adj[1] -> vector and so on.

In second we are making vector of size 10 whose each element will be vector which is equivalent to array of vector as above therefore here also,
adj[0] -> vector
adj[1] -> vector and so on

what should be prefer? arrays of vector or vectors of vectors?

You need to mark the starting vertex as visited initially. Rest seems fine

1 Like

nice…thanks a lot for amazing help.
how can i deal with this bfs problem- https://www.codechef.com/problems/TRATCK1

1 Like

For Breadth First Search the video tutorial link from saurabhschool is BFS

and code implementation is https://github.com/mission-peace/interview/blob/master/C%2B%2B/Graph%20Algorithms/Breadth%20First%20Search.cpp

For Depth First search the video is here DFS
and code is at github https://github.com/mission-peace/interview/blob/master/C%2B%2B/Graph%20Algorithms/Depth%20First%20Search.cpp

In particular for graph problem you can refer this playlist Tushor Roy Graph Tutorial and implementaion in
Tushor Roy Graph Implementation code

and for very basic you can refer this Playlist saurabhschool graph

1 Like

You can use any of them

It is a DFS problem. Simply find the no of components in the graph.