Topological Sort
Authors: Benjamin Qi, Michael Cao, Nathan Chen, Andi Qu, Andrew Wang
An ordering of vertices in a directed acyclic graph that ensures that a node is visited before every node it has a directed edge to.
To review, a directed graph consists of edges that can only be traversed in one direction. Additionally, a acyclic graph defines a graph which does not contain cycles, meaning you are unable to traverse across one or more edges and return to the node you started on. Putting these definitions together, a directed acyclic graph, sometimes abbreviated as DAG, is a graph which has edges which can only be traversed in one direction and does not contain cycles.
Topological Sort
Focus Problem – read through this problem before continuing!
A topological sort of a directed acyclic graph is a linear ordering of its vertices such that for every directed edge from vertex to vertex , comes before in the ordering.
There are two common ways to topologically sort, one involving DFS and the other involving BFS.
Resources | |||
---|---|---|---|
CSA | interactive, both versions |
DFS
Resources | |||
---|---|---|---|
CPH | example walkthrough | ||
CP2 | code | ||
cp-algo | code |
C++
#include <bits/stdc++.h>using namespace std;#define pb push_backint N; // Number of nodesvector<int> graph[100000], top_sort; // Assume that this graph is a DAGbool visited[100000];void dfs(int node) {
Java
import java.util.*;import java.io.*;public class CourseSchedule {public static ArrayList <Integer> g[];public static ArrayList <Integer> topo = new ArrayList < Integer > ();public static int N;public static boolean visited[];public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Finding a Cycle
Focus Problem – read through this problem before continuing!
We can modify the algorithm above to return a directed cycle in the case where a topological sort does not exist. To find the cycle, we add each node we visit onto the stack until we detect a node already on the stack.
For example, suppose that our stack currently consists of and we then visit for some . Then is a cycle. We can reconstruct the cycle without explicitly storing the stack by marking as not part of the stack and recursively backtracking until is reached again.
C++
#include <vector>#include <iostream>#include <algorithm>using namespace std;bool visited[(int)10e5+5], on_stack[(int)10e5+5];vector<int> adj[(int)10e5+5];vector<int> cycle;int N, M;bool dfs(int n) {
Java
import java.io.*;import java.util.*;public class cycle {public static ArrayList < Integer > [] adj;public static boolean visited[], on_stack[];public static ArrayList < Integer > cycle;public static int N, M;public static void main(String[] args) throws IOException {BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
Warning!
This code assumes that there are no self-loops.
BFS
The BFS version, known as Kahn's Algorithm, makes it obvious how to extract the lexicographically minimum topological sort.
C++
int in_degree[100000];vector<int> edge[100000];int N; //number of nodesvoid compute() {queue<int> q;for (int i = 0; i < N; i++) {if (in_degree[i] == 0) {q.push(i);
Java
static int in_degree[];static ArrayList<Integer> edge[]; //adjacency liststatic int N; //number of nodesstatic void topological_sort() {Queue<Integer> q = new ArrayDeque<Integer>();for (int i = 0; i < N; i++) {if (in_degree[i] == 0) {q.add(i);
Dynamic Programming
Resources | |||
---|---|---|---|
CPH |
One useful property of directed acyclic graphs is, as the name suggests, that no cycles exist. If we consider each node in the graph as a state, we can perform dynamic programming on the graph if we process the states in an order that guarantees for every edge that is processed before . Fortunately, this is the exact definition of a topological sort!
Focus Problem – read through this problem before continuing!
In this task, we must find the longest path in a DAG.
Solution
Problems
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
CSES | Easy | Show TagsTopoSort | ||||
Kattis | Easy | Show TagsTopoSort | ||||
Gold | Easy | Show TagsTopoSort | External Sol | |||
Gold | Normal | Show TagsTopoSort, Binary Search | External Sol | |||
CSES | Hard | Show TagsTopoSort |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!
Give Us Feedback on Topological Sort!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.