graph - dfs bfs

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

same problem with BFS - queue

dfsvbfs.jpg

Responses

More Comments
dhrupitdave's picture

Are you asking that how DFS and BFS algorithm works?

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 ?

dhrupitdave's picture

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.

can u provide procedure for finding Strongly connected component

plz...

dhrupitdave's picture

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.

 

Follow below link for more detail...

http://www.techtud.com/computer-science/data-structures#overlay=video-lecture/lecture-data-structures-3

 

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.