トポロジカルソートは、有向グラフの全頂点を「各辺 u → v について必ず u が v より前に来る」ように一列に並べるアルゴリズムです。
本記事では、コピペで使えるトポロジカルソートのライブラリをC++で実装します。
※なお、今回のライブラリは Graph ライブラリが前提となっています。
以下リンクからコピペしてご使用ください↓
・グラフ構造体 をC++で実装してみた
主な機能と計算量
| 名前 | 説明 | 計算量 |
|---|---|---|
topological_sort<T>(g) |
g に対して、トポロジカルソート済みの配列を返す |
$O(V+E)$ |
実装したコード
//----------------ここにGraphライブラリ--------------------//
// https://qiita.com/untan/items/8c561a04b47de49bc2e8 //
//------------------------------------------------------//
template<typename T>
vector<int> topological_sort(Graph<T> &g){
//入次数0の頂点のキュー
queue<int> q;
vector<int> deg_in = g.deg_in();
for(int i=0;i<deg_in.size();i++){
if(deg_in[i] == 0) q.push(i);
}
// トポロジカルソート済みの配列にする予定
vector<int> ret;
// 入次数0キューが空になるまで、入次数0の頂点をretに追加していく
while(!q.empty()){
int i = q.front();
q.pop();
ret.push_back(i);
// iから行ける場所の入次数を1減らし、新しく入次数0になったらキューに追加する
for(pair<T, int> next: g.nexts(i)){
int ni = next.second;
deg_in[ni]--;
if(deg_in[ni] == 0) q.push(ni);
}
}
return ret;
}
使用例
#include<bits/stdc++.h>
using namespace std;
//----------------ここにGraphライブラリ--------------------//
// https://qiita.com/untan/items/8c561a04b47de49bc2e8 //
//------------------------------------------------------//
//--ここにtopological_sortライブラリ--//
// //
//---------------------------------//
int main(void){
// グラフの作成
Graph g(4);
g.add_edge(1, 0); //1 → 0 の辺を追加
g.add_edge(1, 3); //1 → 3 の辺を追加
g.add_edge(3, 2); //3 → 2 の辺を追加
// 各頂点間の最短距離を求める
vector<int> tp = topological_sort(g);
for(int i=0;i<4;i++){
cout << tp[i] << " ";
}// 1 0 3 2と表示される
}
注意点・Tips
- 閉路がある場合、トポロジカルソートした配列
retはret.size() < Nとなります - 逆に言えば、
if(ret.size() < N)などとすれば、閉路があるかの判定ができます