##### graph - dfs bfs during DFS how to put element in stack .&

graph - dfs bfs

during DFS how to put element in stack .  Ascending or Descending order , Or alphabeticaly

same problem with BFS - queue

Ranita Biswas ranita 15 Oct 2014 06:29 pm

Both are correct. But, as a thumb rule ascending or alphabetic ordering is used to put the nodes in the stack or queue; because for each node the edge list is usually stored in that order. So, in general your first (left hand side) approach will be considered correct.

Parimal Andhalkar parimal_andhalkar 15 Oct 2014 08:04 pm

can u provide procedure for finding Strongly connected component

plz.....

Dhrupit Dave dhrupitdave 15 Oct 2014 07:57 pm

Are you asking that how DFS and BFS algorithm works?

Parimal Andhalkar parimal_andhalkar 15 Oct 2014 08:01 pm

yes , i am confuse about the order in which elements placed in stack or queue

i.e. Ascending , descending , or alphabetically,

in some videos i found descending .

which is correct ?

Dhrupit Dave dhrupitdave 16 Oct 2014 09:15 am

The manner in which you can place the nodes to the stack OR queue is purely based on the node connectivity and has no relation to the (Ascending , descending , or alphabetically)order.

With reference to the example you provided I could have solved it this way :-

DFS:- Process start node (2) [o/p - 2] and put 0 and 3 to the stack.(putting in any order is fine and for the GATE, look for the options which one is given. and this is the reason that DFS and BFS are called that they may have different solutions for one problem). i will add (0,3) where 3 is the top of the stack. Process 3 [o/p - 2,3] stack (0) because 3 doesn't have any other non-visit nodes so we will remove 3 from the stack but will not add any other nodes to it. now process 0 [o/p - 2,3,0] stack will be (1). 0 has two connected components 2 and 1. 2 is already processed so i took 1 in the stack. finally process 1. [o/p - 2,3,0,1].

now if you have taken the stack as (3,0) then output can be changed. but in GATE please go through the option for this decission taking solutions.

Same thing applies for the BFS. Instead of stack use queue in the stack and based on the property of the queue process the REAR end and generate the output.

Ask me if you still have any confusions.

Parimal Andhalkar parimal_andhalkar 16 Oct 2014 09:49 am

can u provide procedure for finding Strongly connected component

plz...

Dhrupit Dave dhrupitdave 17 Oct 2014 09:34 am

Considering the attachment you have given Strongly Component can be found as:-

Definition says that "A Subgraph is said to be strongly connected if from each node it can reach to all other nodes". Starting with (2) from the figure. from (2) there is a path to reach (0) only. and from (0) too it has path to reach 2. so, (0,2) will be a strongly connected component. now let take node 1, it can reach out to 2 and 2 reach out to 0 and 0 can reach out to 1. (0,1,2) is also a strongly connected component. now take a last node 3. it can not reach to any other node by looking at the outgoing edges. so, it is individually be a component here.

So, Strongly Connected Components here are :- (0,2) , (1) , (3)  OR (0,1,2) and (3). both seems correct answer.