Topological Sorting
Topological Sorting
1. Basics
(1) Topological Sorting By Breath First Search (Kahn's Algorithm)
Idea:
Create adjacent list for the graph
Calculate the inDegree for each node
Start with node with 0 inDegree and do BFS for its neighbor
Everytime we visit a node, we decrement the inDegree of it by 1, if the inDegree turns to 0, we add the node to queue
import java.util.*;
public static void topologicalSortByBFS(int nodes, int[][] edges) {
List<List<Integer>> adjList = new ArrayList<>();
List<Integer> topologicalSortOrder = new ArrayList<>();
for (int i = 0; i < nodes; i++) {
adjList.add(new ArrayList<>());
}
int[] inDegree = new int[nodes];
for (int[] edge : edges) {
++inDegree[edge[1]];
adjList.get(edge[0]).add(edge[1]);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int curNode = queue.remove();
++count;
topologicalSortOrder.add(curNode);
for (int nextNode : adjList.get(curNode)) {
if (--inDegree[nextNode] == 0) {
queue.add(nextNode);
}
}
}
if (count != nodes) {
System.out.println("Cycle is detected, can not implement topological sort");
}
else {
printTopologicalSortOrder(topologicalSortOrder);
}
}
public static void printTopologicalSortOrder(List<Integer> list) {
System.out.println("Topological Sort: ");
for (int order : list) {
System.out.print(order + " ");
}
}
public static void main(String[] args) {
int nodes = 6;
int[][] edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};
topologicalSortByBFS(nodes, edges);
}
(2) Topological Sorting By Depth First Search
ideas:
Create adjacent list for the graph
Maintain two boolean array visited and visiting, where visited mean a node has been visited from a path in dfs, while visiting means a node is being visited in the dfs
If the visiting value for a node is true, this means a loop is found
If the visited value for a node is true, this means we have visited this node, we can skip it
import java.util.*;
public static void topologicalSortByDFS(int nodes, int[][] edges) {
List<List<Integer>> adjList = new ArrayList<>();
List<Integer> topologicalSortOrder = new ArrayList<>();
for (int i = 0; i < nodes; i++) {
adjList.add(new ArrayList<>());
}
for (int[] edge : edges) {
adjList.get(edge[0]).add(edge[1]);
}
boolean[] visited = new boolean[nodes];
boolean[] visiting = new boolean[nodes];
for (int i = 0; i < nodes; i++) {
if (!dfs(i, visited, visiting, adjList, topologicalSortOrder)) {
System.out.println("Cycle is detected, can not implement topological sort");
return;
}
}
printTopologicalSortOrder(topologicalSortOrder);
}
public static boolean dfs(int curNode, boolean[] visited, boolean[] visiting, List<List<Integer>> adjList, List<Integer> topologicalSortOrder) {
// if curNode has been visited (added to the result), we skip it
if (visited[curNode]) {
return true;
}
// Found loop in the current DFS
if (visiting[curNode]) {
return false;
}
visiting[curNode] = true;
for (int nextNode : adjList.get(curNode)) {
if (!dfs(nextNode, visited, visiting, adjList, topologicalSortOrder)) {
return false;
}
}
visited[curNode] = true;
topologicalSortOrder.add(0, curNode);
return true;
}
public static void printTopologicalSortOrder(List<Integer> list) {
System.out.println("Topological Sort: ");
for (int order : list) {
System.out.print(order + " ");
}
}
public static void main(String[] args) {
int nodes = 6;
int[][] edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};
topologicalSortByDFS(nodes, edges);
}
2. Thoughts
Q:What if the input is not integer, but rather character or string, what data structure should we use to build up adjacent list and inDegree?
A: Use hashmap, for example, if the input is character, then Adjacent list: Map<Character, Set<Character>>, inDegree: Map<Character, Integer>
Q: Time Complexity for Topological Sort:
A: O(n + e), where n is the number of nodes and e is the number of edges
3. Interview Questions
Last updated
Was this helpful?