cycle_detection_undirected
関数 · 有向グラフの閉路検出（閉路を構成する辺 ID 列を返す）
template <graph_type G>
std::pair<std::vector<int>, std::vector<int>> cycle_detection_undirected(const G &g);
概要
無向グラフの閉路検出（閉路を構成する頂点列と辺 ID 列を返す）
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
G |
グラフ型（list_graph<T> / csr_graph<T> のいずれでも可） |
戻り値
{頂点列, 辺 ID 列}。閉路が無ければ両方空。
計算量
- $O(V+E)$
備考
- 無向辺は
list_graph::add_edgesで追加し、往復 2 本に同じ ID が振られていること。 自己ループは長さ 1、多重辺は長さ 2 の閉路として検出する。
関連項目
cycle_detection_directed— 有向グラフの閉路検出（閉路を構成する辺 ID 列を返す）has_cycle— 閉路検出