hello everyone,i have been struggling in graphs for more than 2 months still don’t get anything.I request you all(please please)give me link to your dfs&bfs(which uses vectors of vectors only)so that i can learn.You can add more like djktra’s and prim’s but atleat help me in dfs and bfs.Thanks
See this section of code:
The functions correspond to the respective traversals as the name suggests. I have used array of vectors, you can simply make it vector of vectors, but I find this very easy and comfortable.
I am assuming the input too be this tree:
1
/ \
2 3
/ \ /
4 5 6
or you can say this:
5
1 2
1 3
2 4
2 5
3 6
vector<int>v[100];
map<int,bool>visit;
queue<int>q;
void bfs()
{
visit[0]=1; // mark the source nodes as visited.
while(!q.empty())
{
int s= q.front();
cout<<s<<" ";
q.pop();
for(int i=0; i<v[s].size();i++)
{
if(!visit[v[s][i]])
{
q.push(v[s][i]); // push all the unvisited child nodes in queue
visit[v[s][i]]=1; // mark them visited
}
}
// we visit 2 and 3 after 1, then 4 and 5(queue's top is 2 after 1 is popped). then we visit 6(queue's top is now 3) and likewise it continues. That is we visit all the child node's first and then go further.
}
}
void dfs(int source)
{
if(v[source].empty()) // if we have reached leaf nodes, then return from here
return;
if(!visit[source]) // we should traverse from an unvisited node only
{
visit[source]=1; // mark it as visited
for(int i=0;i<v[source].size();i++)
{
if(!visit[v[source][i]]) // if this child node hasn't been reached by any other node
{
cout<<v[source][i]<<" ";
dfs(v[source][i]); // start recursively from this node now
}
}
}// like in the above example, we start from 1, reach 2, then reach 4. (we didn't go 3 which is the child of 1. After the function returns from 4, we go to 5(the last recursive call at this stage is the recursive call of node 2. After this call returns, we come at the call of node 1 and visit 3 and then 6.
We basically take one child node and explore it further and then go to other child nodes
}
int main()
{
int n,a,b;
cin>>n;
int i;
for(i=0;i<n;i++)
{
cin>>a>>b;
v[a].push_back(b);
}
cout<<"DFS: ";
cout<<"1 ";
dfs(1);
cout<<"\nBFS : ";
visit.clear();
q.push(1);
bfs();
return 0;
}
The code is self-explanatory I suppose, I’ll add on some of it if you want. Just let me know that in comments. 
3 Likes
Follow this blog it might help you… It helped me 
@damn_me or anyone willing to answer,i have seen some people’s code and i found that there are sometime two push_back statements(like v[a].push_back(b) and v[b].push_back(a)) whereas your code have only one.What’s the difference??and secondly can i use this code for weighted graph problem as well or its only for unweighted one :)
this line please “v[a].push_back(b);” little tricky for me
That’s very easy, just assume that you are making array(or you may call vector after changing declaration) for every node. And the array has all the node numbers reachable from that node. I.e. if 1 has 2 and 4 as its child, then v[1] has 2 and 4 in its array (or vector). You’ll get handy with this after some practise.
1 Like
@damn_me i know i am asking for too much but if can add some short comment lines in front of every important step… its okay if you are short of time :)Thanks for the support
@damn_me did you forget to mark nodes visited in dfs portion of your code??i may be wrong but i think there should be statement like " visit[v[source][i]]=1" after “cout<<v[source][i]<<” “;” statement and before recursion.correct me if i am wrong and again thank you so much
See the edit, I think that line mistakenly got deleted while editing!!
1 Like
Basically, what happens is, we have to do traversal on graph that may be directed or undirected. For undirected one, we use the above two push statements, for directed ones, we use one.
1 Like
thanks…what about weighted or unweighted one…
Yes you can, even traversals are maximum times used for problems that involve manipulation like path cost etc…
1 Like
thanks again