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

help
, , , ,
#1

When to apply bfs and dfs? what type of problems are handled by bfs & dfs?
any simple practice problems? I dont want to learn pointers in detail thats why i am interested in stl implementation.Please help me.

5 Likes
#2

Here’s the code to Breadth first Search : https://github.com/Shraeyas/General-Codes/blob/master/bfs.cpp

Here’s the code to Depth first Search : https://github.com/Shraeyas/General-Codes/blob/master/dfs.cpp

For practise you can check this problem on SPOJ : www.spoj.com/problems/PT07Z

It can be done either using BFS or DFS.

1 Like
#3

I have taken the number of vertices as n and the number of edges as m.

And the adjacency list is being denoted by adj.

Visited array is used to check if our current vertex is visited or not.

For DFS :

Since I have taken a map for visited array, all the vertices will be initially marked 0 i.e. unvisited.

Now we will take some starting vertex s (which I have by default to be 1 but you can change it to anything).

Now inside the DFS function :

for(int i=0 ; i< adj[s].size();i++)

	if(!vis[adj[s][i]])
	{
		dfs(adj[s][i]);
	}

If our current edge leads to a vertex which is already visited then we do nothing.

Otherwise if that vertex is unvisited then we will start processing from this vertex, i.e. we will make it our current vertex i.e. further move into recursion making it our starting vertex.

	if(!vis[adj[s][i]])
	{
		dfs(adj[s][i]);
	}

When all the vertices for current vertex are visited then we will start backtracking.

Now this same process will be carried out again and again until all the vertices are visited.

For BFS :

Similar to DFS, initially all the vertices are marked 0 i.e. unvisited.

Just similar to how we used recursion in DFS, here we will make use of a queue.

BFS processes a graph level by level.

First we take a starting vertex s, and push it onto queue and mark it as visited.

Now we will process the graph until the queue is empty.

We will take all the vertices which are directly attached to the vertex on top of the queue.

for(int i=0;i< adj[s].size();i++)

  	if(!vis[adj[s][i]])

		{
			cout<<adj[s][i]<<" ";
			
			vis[adj[s][i]] = 1;
			q.push(adj[s][i]);
		}

Now if the vertices are unvisited they are pushed into the queue.

Now we will perform pop operation on the queue and remove the topmost element of the queue and repeat the above two steps again again until all the vertices are visited.

Thats it!

4 Likes
#4

You could refer these links:

GeeksForGeeks Link
Link 2

Simple STL Explanation from TopCoder

BFS with STL

For questions, you could just sort down on Codechef, Codeforces I guess based on BFS/ DFS tags.

6 Likes
#5

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
#6

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
#7

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
#8

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
#9

Hey Buddy i was also stuck to implement dfs. but i got exact way to come out. Go for these tutorials will get u know about both implementation and explanation.

[link 1][1]

[link 2][2]

it will help u lot :slight_smile:
[1]: https://youtu.be/uT1p5Eiw9CE
[2]: https://youtu.be/fI6X6IBkzcw

#10

can u please explain the code little bit.can i able to solve any problem with dfs or bfs at codechef

#11

One question before that… are you completely new to BFS and DFS and want me to explain those algorithms also or you just want the explanation for the code?

1 Like
#12

yes completely new to dfs and bfs,i just want to increase my level

#13

Then I would suggest you to watch video tutorials on youtube and then try to understand the code. This way it would be better.

If you understand the algorithm properly then you will surely understand the code. It’s very straight forward :slight_smile:

#14

But If you insist I can explain the codes but I guess it would be better the other way, i.e. first the algo and then the code.

#15

i already knows about the algorithm,but plz explain me code because for full clearity purpose

#16

OK, give me a few minutes :slight_smile:

#17

sure…it will be okay to use dfs,bfs through stl in contests?

#18

Yes, STL will definitely be good to use for contests, it saves you a lot of time.

For example you want to implement dijkstra somewhere and if you go for implementing priority queue by yourself then it will eat up a lot of time and if any error creep in there you might also have to debug that part too. So it’s better to go with STL

1 Like
#19

what if i take arrays of vector,since im unable to understand some lines(meaning).please help me

#20

but i am unable to figure out how to apply,please help me