Let $G$ be a digraph. The topological sorting algorithm is a linear ordering of the vertices of $G$ such that for every directed edge $u\to v$, where $u,v\in V(G)$, $u$ comes before $v$ in the ordering. The ordering is possible only if the graph has no directed cycles.

• Since the graph has no directed cycles, at least one of the vertices has no incoming edges.

vector<bool> visited;
// adjacency list of G
vector<vector<int> > g;
vector<int> order;

void dfs(int v) {
  visited[v] = true;
  for (int i = 0; i < g[v].size(); i += 1) {
    int next = g[v][i];
    if (!visited[next]) {
      dfs(next);
    }
  }
  order.push_back(v);
}

/**
 * Given a graph `G` of order `n` and size `m` computes a linear ordering
 * of the vertices such that for every edge u -> v, `u` comes earlier than `v`
 * in the ordering
 *
 * Time complexity: O(n + m)
 * Space complexity: O(n)
 *
 */
void topological_sort() {
  int n = g.size();
  visited.assign(n, false);

  for (int i = 0; i < visited.size(); i += 1) {
    if (!visited[i]) {
      dfs(i);
    }
  }

  reverse(order.begin(), order.end());
}

Applications

Shortest path in a Directed Acyclic Graph

// adjacency list of G
// (to, weight)
vector<vector<pair<int, int> > > g;

// topological sort states
vector<bool> visited;
vector<int> order;

// shortest path state
vector<int> dist;

void dfs(int v) {
  visited[v] = true;
  for (int i = 0; i < g[v].size(); i += 1) {
    int next = g[v][i];
    if (!visited[next]) {
      dfs(next);
    }
  }
  order.push_back(v);
}

void topological_sort() {
  int n = g.size();
  visited.assign(n, false);

  for (int i = 0; i < visited.size(); i += 1) {
    if (!visited[i]) {
      dfs(i);
    }
  }

  reverse(order.begin(), order.end());
}

/**
 * Given a weighted graph `G` of order `n` and size `m` and a source vertex `source`
 * it computes the shortest distance between `source` and every other reachable
 * vertex from `source`
 *
 * Time complexity: O(n + m)
 * Space complexity: O(n)
 *
 */
void shortest_path_dag(int source) {
  int n = g.size();
  dist.assign(n, -1);

  topological_sort();
  dist[source] = 0;

  for(int i = 0; i < order.size(); i += 1) {
    int v = order[i];
    if (dist[v] >= 0) {
      for (int j = 0; j < g[v].size(); j += 1) {
        int to = g[v][j].first;
        int weight = g[v][j].second;
        int path_distance = dist[v] + weight;
        if (dist[to] < 0 || dist[to] > path_distance) {
          dist[to] = path_distance;
        }
      }
    }
  }
}