Topological sorting by reference counting. Orders the nodes of a DAG so that all edges go from left to right. This
is done by counting the number of in-edges at each node. The nodes with an in-degree of zero are kept in a queue
(could just be a set; the order doesn’t matter). Nodes are taken from the queue and placed in the topological sorted
order. As you do so, you decrement the counts for the nodes that this node has edges to. If any of them reaches zero,
they are placed in the queue. (See Chapter 4.)
Do'stlaringiz bilan baham: |