tree_bfs

関数 · 木の基本関数

// (1)
template <graph_type G>
std::vector<int> tree_bfs(const G &g, int r = 0);

// (2)
std::vector<int> tree_bfs(const std::vector<int> &parents);

概要

(1) 根rからのBFS順を返す

• テンプレートパラメータ G: グラフ型（list_graph<T> / csr_graph<T> のいずれでも可）
• 計算量: $O(V+E)$

(2) 親配列が表す木のBFS順を返す

• 計算量: $O(V)$

関連項目

• tree_dfs — 根rからのDFS行きがけ順を返す
• tree_dist — 木の距離を求める
• tree_parent — 木の頂点の親を求める
• tree_subtree — 部分木の大きさを求める