Rare

0/8

Topological Sort

Authors: Benjamin Qi, Michael Cao, Nathan Chen, Andi Qu, Andrew Wang

Prerequisites

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.

Topological Sort DFS Finding a Cycle BFS Dynamic Programming Problems

Edit on Github

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

Course Schedule

CSES - Easy

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 $u\to v$ from vertex $u$ to vertex $v$ , $u$ comes before $v$ in the ordering.

There are two common ways to topologically sort, one involving DFS and the other involving BFS.

Resources
CSA	Topological Sorting	interactive, both versions

DFS

Resources
CPH	16.1 - Topological Sort	example walkthrough
CP2	4.2.5 - Topological Sort	code
cp-algo	Topological Sort	code

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4#define pb push_back
5
6int N; // Number of nodes
7vector<int> graph[100000], top_sort; // Assume that this graph is a DAG
8bool visited[100000];
9
10void dfs(int node) {

Java

1import java.util.*;
2import java.io.*;
3
4public class CourseSchedule {
5    public static ArrayList <Integer> g[];
6    public static ArrayList <Integer> topo = new ArrayList < Integer > ();
7    public static int N;
8    public static boolean visited[];
9    public static void main(String[] args) throws Exception {
10        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

Finding a Cycle

Round Trip II

CSES - Easy

Focus Problem – read through this problem before continuing!

We can modify the algorithm above to return a directed cycle in case 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. Once we find the cycle exists, we mark the start of the cycle as not part of the stack and revursively backtrack until we reach the start node again.

C++

1#include <vector>
2#include <iostream>
3#include <algorithm>
4using namespace std;
5
6bool visited[(int)10e5+5], on_stack[(int)10e5+5];
7vector<int> adj[(int)10e5+5];
8vector<int> cycle;
9int N, M;
10bool dfs(int n) {

Java

1import java.io.*;
2import java.util.*;
3
4public class cycle {
5    public static ArrayList < Integer > [] adj;
6    public static boolean visited[], on_stack[];
7    public static ArrayList < Integer > cycle;
8    public static int N, M;
9    public static void main(String[] args) throws IOException {
10        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));

BFS

The BFS version, known as Kahn's Algorithm, makes it obvious how to extract the lexicographically minimum topological sort.

C++

1int in_degree[100000];
2vector<int> edge[100000];
3
4int N; //number of nodes
5
6void compute() {
7    queue<int> q;
8    for (int i = 0; i < N; i++) {
9        if (in_degree[i] == 0) {
10            q.push(i);

Java

1static int in_degree[];
2static ArrayList<Integer> edge[]; //adjacency list
3
4static int N; //number of nodes
5
6static void topological_sort() {
7    Queue<Integer> q = new ArrayDeque<Integer>();
8    for (int i = 0; i < N; i++) {
9        if (in_degree[i] == 0) {
10            q.add(i);

Dynamic Programming

Resources
CPH	16.2 - Dynamic Programming

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 $u\to v$ that $u$ is processed before $v$ . Fortunately, this is the exact definition of a topological sort!

Longest Flight Route

CSES - Easy

Focus Problem – read through this problem before continuing!

In this task, we must find the longest path in a DAG.

Solution

Problems

Source	Problem Name	Difficulty	Tags	Solution
CSES	Game Routes	Easy	Show Tags TopoSort	Internal Sol
Kattis	Quantum Superposition	Easy	Show Tags TopoSort	Internal Sol
Gold	Timeline	Easy	Show Tags TopoSort	External Sol
Gold	Milking Order	Normal	Show Tags TopoSort, Binary Search	External Sol
CSES	Course Schedule II	Hard	Show Tags TopoSort	Internal Sol

Module Progress:

Give Us Feedback on Topological Sort!

Topological Sort DFS Finding a Cycle BFS Dynamic Programming Problems Edit on Github

Topological Sort

Prerequisites

Table of Contents

Topological Sort

DFS

Finding a Cycle

BFS

Dynamic Programming

Problems

Module Progress:

Give Us Feedback on Topological Sort!

Table of Contents

Topological Sort

Prerequisites

Table of Contents

Topological Sort

DFS

Finding a Cycle

BFS

Dynamic Programming

Problems

Module Progress:Not Started

Give Us Feedback on Topological Sort!

Table of Contents

Module Progress: