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

help
, , , ,
21

Definitely that can be done. You can use an array of vectors.

vectoradj(100);

It will work exactly the same.

22

Firstly, vector adj[V]; defines a List container which shall keep the stored nodes and the list stored shall be of the nodes which are directly connected to it. Secondly, another approach for weighted graph is to Store weight using a vector adj[V]; where suppose for a node U you can have (edge, weight) stored all along. Then adj[U].push_back(V); stores V as a node connected to U with a direction from U --> V for undirected do the same pushback swapping U, V again. Simply, use a list iterator to traverse through the connected nodes for DFS which should suffice.

1 Like
23

Using Lists in DFS/BFS reduces Time/ Space complexity by a huge efficiency. you can’t even store weights for graphs with vertices over 10^5 because you’d have to create COST[100000][100000] which shall result in StackOverFlow error. But using PAIR as i mentioned above solves all the problem. Refer through the links I mentioned above, they’ll provide you an optimum approach to make you understand.

1 Like
24

then role of map? please dont mind…But nice explanation

25

map is more useful when the limits on inputs are too high. For example you can’t take an array of size 10^9 but with map you can do it directly.

So it’s just the size, which is why I used map. But you can replace map with vector of array here. It doesn’t really matter :slight_smile:

26

please provide vector implementation im unable to understand role of map

27

Ok, I will update that.

28

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

29

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

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

30

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

31

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

32

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

33

what is wrong in this code 1uOMcF - Online C++ Compiler & Debugging Tool - Ideone.com

34

code link-1uOMcF - Online C++ Compiler & Debugging Tool - Ideone.com

35

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.

36

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

37

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

38

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

1 Like
39

nice…thanks a lot for amazing help.
how can i deal with this bfs problem- TRATCK1 Problem - CodeChef

1 Like
40

You can use any of them