C++で依存関係からタスクの実行順序を見つける方法（トポロジカルソート）

問題概要

n個の異なるタスクがあるとします。各タスクには0からn-1までのラベルが付けられており、一部のタスクには前提条件（先に完了しておく必要のあるタスク）が存在します。例えば、タスク2を選択したい場合は、まずタスク1を完了していなければなりません。この関係はペア [2, 1] として表現されます。

タスクの総数と前提条件ペアのリストが与えられたとき、すべてのタスクを完了できるような実行順序を見つける必要があります。有効な順序が複数存在する場合は、そのうちのどれか1つを返せば構いません。また、与えられたすべてのタスクを完了することが不可能な場合（循環依存が存在する場合）は、空の配列を返します。

例えば、入力が n = 4、A = [[1, 0], [2, 0], [3, 2], [3, 1], [4, 2]] の場合、出力は [0, 2, 1, 4, 3] のようになります。

アルゴリズム：DFSによるトポロジカルソート

この問題は、グラフ理論における「トポロジカルソート」の手法で解くことができます。DFS（深さ優先探索）を用いて循環を検出しながら、依存関係に基づいたタスクの順序を構築していきます。

dfs()関数の手順

1. dfs()関数を定義します。この関数は、グラフ、開始ノード start、onpath 配列、visited 配列、toposort 配列を引数として受け取ります。
2. visited[start] がすでにマークされている場合は、false を返します。
3. onpath[start] := true、visited[start] := true と設定します。
4. graph[start] 内の各隣接ノード neighbor について、以下を確認します。
   • onpath[neighbor] が true、または dfs(graph, neighbor, onpath, visited, toposort) の結果が true の場合は、true を返します（循環が検出されたことを意味します）。
5. start を toposort の末尾に挿入します。
6. onpath[start] := false として、false を返します。

メイン処理の流れ

1. pre 配列に格納された辺を持つ、n 頂点のグラフを作成します。
2. toposort 配列を定義します。
3. サイズ n の onpath 配列を false で初期化します。
4. サイズ n の visited 配列を false で初期化します。
5. i := 0 から i < n まで、i を 1 ずつ増やしながら以下を繰り返します。
   • visited[i] が false であり、かつ dfs(graph, i, onpath, visited, toposort) が true を返した場合は、空の配列を返します。
6. toposort 配列を反転します。
7. toposort を返します。

なお、このアルゴリズムの計算量は、頂点数を V、辺数を E とすると時間・空間ともに O(V + E) となり、非常に効率的です。

C++での実装例

以下の実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
vector<unordered_set<int> > create_graph(int n, vector<pair<int, int> >& pre) {
   vector<unordered_set<int> > graph(n);
   for (auto pre : pre)
      graph[pre.second].insert(pre.first);
   return graph;
}
bool dfs(vector<unordered_set<int> >& graph, int start,vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) {
   if (visited[start])
      return false;
   onpath[start] = visited[start] = true;
   for (int neigh : graph[start])
      if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
         return true;
   toposort.push_back(start);
   return onpath[start] = false;
}
vector<int> get_order(int n, vector<pair<int, int> > &pre){
   vector<unordered_set<int> > graph = create_graph(n, pre);
   vector<int> toposort;
   vector<bool> onpath(n, false), visited(n, false);
   for (int i = 0; i < n; i++)
      if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
         return {};
   reverse(toposort.begin(), toposort.end());
   return toposort;
}
int main() {
   int n = 4;
   vector<pair<int, int> > pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}};
   vector<int> v = get_order(n, pre);
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << " ";
   }
}

入力

4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}

出力

0 1 4 2 3