Definition of Topological Sort
The topological sort of a DAG G(V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v), then u appears before v in the ordering.
Mathematically, this ordering is described by a function t that maps each vertex to a number
t: V → (1, 2,..., n): t(v) i such that t(u) < t(v) < t(w) for the vertices u, v, w of the following diagram:
In the above diagram, we see that the node u has no incoming edge, and u comes first as above said, so the node u is removed and added to the topological sort order as u now the node v comes, it also not has incoming edges so, node v is removed and update the topological sort order as uv. Similarly, for the last node, the topological sort order is uvw.
Download Formulas for GATE Computer Science Engineering - Algorithms
Topological Sort using DFS
The topological sort time complexity using DFS takes θ(m+n) time, and the insertion of each vertex to the linked list takes O(1) time. Thus, topological sort using DFS takes time θ(m + n). The following algorithm is as follows:
1. Perform DFS to compute finishing times f[v] for each vertex v
2. As each vertex is finished, insert it to the front of a linked list
3. Return the linked list of vertices
Topological Sort using Bucket Sorting
This algorithm computes a topological sort of a DAG beginning from a source and uses bucket sorting to arrange G nodes by their in-degree (# incoming edges).
An array of lists of nodes forms the bucket structure. Each node also maintains links to the vertices (nodes) to which its outgoing edges lead. The lists are sorted so that all vertices with n incoming edges lay on the list at the nth position of the table, as shown in the figure:
Download Formulas for GATE Computer Science Engineering - Discrete Mathematics
The main idea is to exclude a node that does not depend on any other at each step. That maps to removing an entry v1 from the 0th index of the bucket structure (which contains the sources of G) and reducing by one the in-degree of the entry's adjacent nodes and reallocating them in the bucket. This means that node v2 is moved to the list at the 0th index and thus becomes a source. v3 is moved to the list at the 1st index, and v4 is moved to the list at the 2nd index. After subtracting the source from the graph, new sources may appear because the source edges are excluded from the graph, or there is more than one source. Thus the algorithm subtracts a source at every step and inserts it into a list until no sources (and consequently no nodes) exist. The resulting list represents the topological sort of the graph.
|Important Topics for Gate Exam|
|Responsivity||Types Of Governors|
|SR Flip-Flop||Types Of Vibration|
|Norton's Theorem||Welded Joints|
|P N Junction Diode||Round Robin Scheduling|
|Classless Addressing||Scaling In Computer Graphics|
Commentswrite a comment