Topological Sort
Topological sort is an ordering of vertices in a directed acyclic graph (DAG) such that for every edge u→v, u comes before v. It's used in scheduling, dependency resolution, and build systems.
Kahn's Algorithm (BFS-based)
1. Compute in-degree of each node.
2. Add nodes with in-degree 0 to queue.
3. While queue not empty, remove node, add to result, reduce in-degree of neighbors; if neighbor becomes 0, add to queue.
4. If result size != V, cycle exists.
Java implementation:
public int[] topologicalSortKahn() {
int[] inDegree = new int[V];
for (int i = 0; i < V; i++) {
for (int v : adjList[i]) inDegree[v]++;
}
Queue q = new LinkedList<>();
for (int i = 0; i < V; i++) if (inDegree[i] == 0) q.offer(i);
int[] result = new int[V];
int idx = 0;
while (!q.isEmpty()) {
int u = q.poll();
result[idx++] = u;
for (int v : adjList[u]) {
if (--inDegree[v] == 0) q.offer(v);
}
}
if (idx != V) throw new RuntimeException("Graph has a cycle");
return result;
}
Two Minute Drill
- Topological sort only possible in DAGs.
- Kahn's algorithm: use in-degree and queue.
- Time O(V+E), space O(V).
- Used in scheduling, course prerequisites, build systems.
Need more clarification?
Drop us an email at career@quipoinfotech.com