Answer Happy

Problem 2. (15 pts Minimum Lexicographic Ordering] A potential problem with topological sorting is that the same graph may have more than one valid ordering of the vertices. 1 2 3 4 5 6 7 In the graph above, for example, {1,2,3,4,5,6,7} is a valid ordering, but so is {2,1,3,4,6,5,7} or {2,1,3,4,6,7,5). To avoid ambiguity, it is common practice to ask for the Minimum Lexicographic Ordering of a graph. Lexicographical order is defined in following way: When we compare s and t, first we find the leftmost position with differing vertices: si #ti. If si <ti, or the label of the i-th vertex in ordering s is smaller than the label of the i-th vertex in ordering t, then ordering s is said to be lexicographically smaller than ordering t. Explain how you would modify the standard topological sorting algorithm to output the lexicographically minimum valid topological ordering of the vertices of a graph. The modified algorithm may take time O(IV+ E| log |V]).