I knew the time complexity of Topological ordering is O(V+E) since we don't need to do sorting during the selection of node whose incoming degree is 0. But what about the least topological ordering that make sure every node to delete is always the least one of the List of 0 incoming degree nodes.
Like the picture show below, "1 2 4 3 5" and "2 1 4 3 5" are both topological ordering but the least one is "1 2 4 3 5".
enter image description here
我将0个传入的度 node 存储在一个优先级队列(min—Heap)中,每次都删除它的顶部.因此,总共有V个 node 要删除,并且每个删除都需要优先级队列O(log V)来调整,以保持其自身为min—Heap.总 node 删除似乎是O(VlogV) while the basic topological ordering is O(V+E). What is the exactly time complexity of The least topological ordering? Is it O(VlogV + E)?希望你能帮我!