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 \rightarrow 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;
        }
      }
    }
  }
}