- Problem 2 15 Pts Minimum Lexicographic Ordering A Potential Problem With Topological Sorting Is That The Same Graph 1 (89.25 KiB) Viewed 48 times
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. 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 compares and t, first we find the leftmost position with differing vertices: 8; ‡ tį. If s¡ < tį, 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(V+ Elog |VI).