WikiGalaxy
Graph Topological Sorting
Understanding Topological Sorting:
Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge UV from vertex U to vertex V, U comes before V in the ordering. It is crucial in scenarios where certain tasks must be performed before others.
Applications:
Topological sorting is used in scheduling tasks, resolving symbol dependencies in linkers, and determining the order of compilation tasks.
import java.util.*;
class Graph {
private int V;
private LinkedList adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void topologicalSortUtil(int v, boolean visited[], Stack stack) {
visited[v] = true;
Integer i;
Iterator it = adj[v].iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
stack.push(new Integer(v));
}
void topologicalSort() {
Stack stack = new Stack();
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
while (stack.empty() == false)
System.out.print(stack.pop() + " ");
}
public static void main(String args[]) {
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Following is a Topological Sort");
g.topologicalSort();
}
}
Example Explanation:
This example demonstrates a graph with 6 vertices. The topological sort function processes each vertex and adds it to a stack, ensuring that all dependencies are resolved before a vertex is added. The stack is then printed in reverse order to produce the topological sort.
Console Output:
5 4 2 3 1 0
Topological Sorting with DFS
Depth-First Search (DFS) Approach:
The DFS approach involves visiting each node and recursively visiting all its adjacent nodes before marking the node as visited. This ensures that all dependencies are resolved before the node is added to the result.
import java.util.*;
class GraphDFS {
private int V;
private LinkedList adj[];
GraphDFS(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void topologicalSortUtil(int v, boolean visited[], Stack stack) {
visited[v] = true;
Integer i;
Iterator it = adj[v].iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
stack.push(new Integer(v));
}
void topologicalSort() {
Stack stack = new Stack();
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
while (stack.empty() == false)
System.out.print(stack.pop() + " ");
}
public static void main(String args[]) {
GraphDFS g = new GraphDFS(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Following is a Topological Sort using DFS");
g.topologicalSort();
}
}
Example Explanation:
This implementation uses DFS to perform a topological sort. The process ensures that each vertex is processed only after all its dependencies are resolved.
Console Output:
5 4 2 3 1 0
Kahn's Algorithm for Topological Sorting
Kahn's Algorithm:
Kahn's algorithm is an iterative method to perform topological sorting. It uses an in-degree array to track the number of incoming edges for each vertex. Vertices with zero in-degree are processed first.
import java.util.*;
class GraphKahn {
private int V;
private LinkedList adj[];
GraphKahn(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void topologicalSort() {
int in_degree[] = new int[V];
for (int i = 0; i < V; i++) {
for (int node : adj[i]) {
in_degree[node]++;
}
}
Queue queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (in_degree[i] == 0)
queue.add(i);
}
int cnt = 0;
Vector topOrder = new Vector<>();
while (!queue.isEmpty()) {
int u = queue.poll();
topOrder.add(u);
for (int node : adj[u]) {
if (--in_degree[node] == 0)
queue.add(node);
}
cnt++;
}
if (cnt != V) {
System.out.println("There exists a cycle in the graph");
return;
}
for (int i : topOrder) {
System.out.print(i + " ");
}
}
public static void main(String args[]) {
GraphKahn g = new GraphKahn(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Topological Sort using Kahn's Algorithm:");
g.topologicalSort();
}
}
Example Explanation:
Kahn's algorithm calculates the in-degree of each vertex and processes vertices with zero in-degree first. This ensures that all dependencies are resolved before a vertex is processed.
Console Output:
4 5 0 2 3 1
Handling Cycles in Topological Sorting
Cycle Detection:
Topological sorting is only possible for Directed Acyclic Graphs (DAGs). If a cycle is detected during the topological sort process, it indicates that a valid ordering is not possible.
import java.util.*;
class GraphCycle {
private int V;
private LinkedList adj[];
GraphCycle(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
boolean isCyclicUtil(int v, boolean visited[], boolean recStack[]) {
if (recStack[v])
return true;
if (visited[v])
return false;
visited[v] = true;
recStack[v] = true;
List children = adj[v];
for (Integer c : children)
if (isCyclicUtil(c, visited, recStack))
return true;
recStack[v] = false;
return false;
}
boolean isCyclic() {
boolean visited[] = new boolean[V];
boolean recStack[] = new boolean[V];
for (int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;
return false;
}
public static void main(String args[]) {
GraphCycle g = new GraphCycle(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
if (g.isCyclic())
System.out.println("Graph contains cycle");
else
System.out.println("Graph doesn't contain cycle");
}
}
Example Explanation:
This example checks for cycles in a graph using DFS. If a cycle is detected, it indicates that topological sorting cannot be performed.
Console Output:
Graph contains cycle
Topological Sorting with BFS
Breadth-First Search (BFS) Approach:
The BFS approach to topological sorting uses a queue to process nodes with zero in-degree, ensuring all dependencies are resolved before processing a node.
import java.util.*;
class GraphBFS {
private int V;
private LinkedList adj[];
GraphBFS(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void topologicalSort() {
int in_degree[] = new int[V];
for (int i = 0; i < V; i++) {
for (int node : adj[i]) {
in_degree[node]++;
}
}
Queue queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (in_degree[i] == 0)
queue.add(i);
}
int cnt = 0;
Vector topOrder = new Vector<>();
while (!queue.isEmpty()) {
int u = queue.poll();
topOrder.add(u);
for (int node : adj[u]) {
if (--in_degree[node] == 0)
queue.add(node);
}
cnt++;
}
if (cnt != V) {
System.out.println("There exists a cycle in the graph");
return;
}
for (int i : topOrder) {
System.out.print(i + " ");
}
}
public static void main(String args[]) {
GraphBFS g = new GraphBFS(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Topological Sort using BFS:");
g.topologicalSort();
}
}
Example Explanation:
This BFS-based topological sorting uses a queue to process nodes with zero in-degree. It ensures that all dependencies are resolved before processing a node.
Console Output:
4 5 0 2 3 1
