Saturday, March 10, 2012

Iterative DFS on acyclic graph.


Input:
first line contains the number of nodes
then n (number of nodes) rows follow depicting the list of nodes connected to a node X. - this is adjacency list representation.
A B C D -> number of nodes.
A B D -> node A is connected to B and D.
B A C  -> node B is connected to A and C.
C B D -> node C is connected to B and D.
D A C B -> node D is connected to A and C.


printing adjacency list: 
A B D 
B A C 
C B D 
D A C 
printing DFS: 
A B C D 


Another Example:
A B C D E F G
A B C D
B E
C F
D G
E
F
G
printing adjacency list: 
A B C D 
B E 
C F 
D G 



printing DFS: 
A D G C F B E 

No comments:

Post a Comment