Topological Sorting
In graph theory, topological sorting is the linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles. Topological sorting has many applications, especially in scheduling problems, dependency analysis, and task ordering.
Topological sorting can be performed using various algorithms, including depth-first search (DFS) and breadth-first search (BFS). The algorithm we will focus on is based on DFS.
Here's an example implementation of topological sorting in Java:
TEXT/X-JAVA
1<<code>>xxxxxxxxxx60
}class Graph { private int V; // No. of vertices private LinkedList<Integer> adj[]; // Adjacency List 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<Integer> stack) { visited[v] = true; Integer i; Iterator<Integer> it = adj[v].iterator(); while (it.hasNext()) { i = it.next(); if (!visited[i]) topologicalSortUtil(i, visited, stack); } stack.push(new Integer(v)); } void topologicalSort() {OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment