reset password
Author Message
G190852562
Posts: 162
Posted 12:39 Dec 08, 2014 |

2. Which of the following are valid topological sorts?

A.

       [([] -> a{1} -> [b{3}, c{2}]), 
        ([a{1}] -> b{3} -> [d{6}, e{5}, f{4}]), 
        ([a{1}] -> c{2} -> []), 
        ([b{3}] -> d{6} -> []), 
        ([b{3}] -> e{5} -> [g{7}]), 
        ([b{3}] -> f{4} -> [g{7}]), 
        ([e{5}, f{4}] -> g{7} -> [])]
 

B.

       [([] -> a{1} -> [b{3}, c{2}]), 
        ([a{1}] -> b{3} -> [d{7}, e{6}, f{4}]), 
        ([a{1}] -> c{2} -> []), 
        ([b{3}] -> d{7} -> []), 
        ([b{3}] -> e{6} -> [g{5}]), 
        ([b{3}] -> f{4} -> [g{5}]), 
        ([e{6}, f{4}] -> g{5} -> [])]
        
 A and B
 A but not B
 Not A but B
 Neither A nor B
 
 I didn't really understand how to read this diagram. What I know about topological sorting is that each edge is pointing forward which seems to be the case with what's going on here.
 
 6. The code for topoSort (Topological Sort) given on the wiki page includes the following line.

for (Node n : nodes.values()) 
What does nodes.values() refer to?

 The set of Nodes associated with Node n stored as a static element of the Node class
 The set of values of the nodes Map in an instance of the Graph class
 The set of values of the nodes Map stored as a static element of the Graph class 
 The set of edges associated with Node n
 
 I know that the answer for this exercise is the 2nd option. But why?