Latest revision |
Your text |
Line 18: |
Line 18: |
| ===Uniqueness=== | | ===Uniqueness=== |
| In general, the topological ordering is ''not'' unique; there may be several different orders in which the graph may be traversed that satisfy the topological ordering property. It ''is'', however, unique if and only if the [[partial order]] represented by the DAG is in fact a total order; that is, when the DAG has a Hamiltonian path, or, equivalently, the [[transitive closure]] of the DAG is the complete graph. | | In general, the topological ordering is ''not'' unique; there may be several different orders in which the graph may be traversed that satisfy the topological ordering property. It ''is'', however, unique if and only if the [[partial order]] represented by the DAG is in fact a total order; that is, when the DAG has a Hamiltonian path, or, equivalently, the [[transitive closure]] of the DAG is the complete graph. |
− |
| |
− | ==Algorithm==
| |
− | The algorithm for generating a topological ordering is embedded in the proof of the Theorem above:
| |
− | # Start with an empty list.
| |
− | # Find a source of the DAG. Add this vertex to the end of the list.
| |
− | # Remove the vertex and all incident edges.
| |
− | # If the DAG is nonempty, go back to step 2.
| |
− | After the termination of this procedure, the list will contain a topological ordering of the DAG.
| |
− |
| |
− | In order to implement this algorithm efficiently, we will not actually remove vertices from the graph in step 3, since this is a computationally expensive operation if the graph is represented as an adjacency matrix or an adjacency list. Nor will we scan through the entire graph each time step 2 is executed in order to find a source; this, too, is computationally expensive. Instead, we make the following observations, in this order:
| |
− | # A vertex is a source if and only if its in-degree is zero.
| |
− | # If a vertex is not originally a source, it will become one after all its incoming edges have been deleted. An incoming edge is deleted only when the vertex at the other side is removed.
| |
− | # Suppose we know where all the sources are in the DAG, and we execute steps 2 and 3 once. After this, the only vertices that might become sources are the ones with an incoming edge from the vertex just removed.
| |
− | Here, then, is a realistic implementation:
| |
− | <pre>
| |
− | for u ∈ V(G)
| |
− | indegree[u] ← 0
| |
− | for (u,v) ∈ E(G)
| |
− | indegree[v] ← indegree[v]+1
| |
− | let C be an empty container
| |
− | let L be an empty list
| |
− | for u ∈ V(G)
| |
− | if indegree[u] = 0
| |
− | insert u into C
| |
− | while C is not empty
| |
− | u ← some element of C
| |
− | remove u from C
| |
− | add u to the end of L
| |
− | for each v ∈ V(G) such that (u,v) ∈ E(G)
| |
− | indegree[v] ← indegree[v]-1
| |
− | if indegree[v] = 0
| |
− | insert v into C
| |
− | if |L| < |V(G)|
| |
− | print "Error: graph contains a cycle"
| |
− | </pre>
| |
− | To implement this efficiently, we will need to be able to iterate through the neighbors of a vertex efficiently. This is best done using an adjacency list. Also, <code>C</code> should be a [[stack]] or a [[queue]], so that insertion and removal of elements can be accomplished in constant time. With that, notice that the first for loop takes <math>O(V)</math> time, the second <math>O(E)</math> time, and the third <math>O(V)</math> time; the while loop runs once for each vertex removed from the container, which only occurs <math>O(V)</math> times, since each vertex is inserted at most once (either at the beginning or just after the last incoming edge is removed), and each edge is examined at most once in the while loop (when the vertex it leaves is popped). Overall, then, this algorithm takes <math>O(E+V)</math> time (linear).
| |
− |
| |
− | The algorithm will always find a topological ordering if one exists. If one does not exist, the list <code>L</code> will not be fully populated, and an error message will be printed.
| |
− |
| |
− | The topological ordering will be unique if and only if <code>C</code> contains exactly one vertex at the beginning of each iteration of the while loop. The proof is left as an exercise to the reader.
| |
− |
| |
− | ''Theorem'': A topological ordering can also be obtained by running [[depth-first search]] and then reversing the postordering generated.
| |
− |
| |
− | ''Proof'': This is equivalent to the statement that if the edge <math>u-v</math> exists then <math>u</math> has a higher postorder number than <math>v</math>. So consider the DFS tree. If <math>u</math> is an ancestor of <math>v</math>, then <math>u</math> has a higher postorder number, as desired. If <math>u</math> is a descendant of <math>v</math> in the DFS tree, then a cycle exists from <math>u</math> back to itself, a contradiction. And if neither <math>u</math> nor <math>v</math> is an ancestor of the other, then <math>u-v</math> is a cross edge, and <math>u</math> has a higher postorder number, as desired. <math>_\blacksquare</math>
| |
− |
| |
− | ==External links==
| |
− | * {{SPOJ|PFDEP|Project File Dependencies}}
| |
− | * {{SPOJ|DEPEND|Dependency Problems}}
| |