グラフは木である
ここで言うグラフは、グラフ理論で言うところのグラフのことで、頂点（ノード）同士を辺（エッジ）で連結させて構成される。
木はグラフの一種で、「閉路を持たず、連結である」という特徴を持つ。
根付木を作る
木は閉路を持たず、連結であるので、逆方向（子→親）に進む以外に、一度見た頂点が再び現れることはない。したがって、次に進む頂点と今の頂点（親）を持っておけば、親→子を辿っていくことができる。
vector<vector<int>> tree(n); /* tree graph of n elements */
queue<pair<int, int>> q; /* node (with parent node) */
q.push({0, -1}); /* 0: root, -1: prarent(none) */
while (!q.empty()) {
pair [u, p] = q.fromt(); /* node u (with parent node) */
q.pop();
for (int v : g[u]) { /* next node */
if (v == p) /* if return to parent node */
continue;
tree[u].push_back(v); /* add child v to u(parent) */
q.push({v, u}); /* go to next node v */
}
}
0を根とした木は、
のようになる。2を根とした場合の木は、
となる。
木の構造を表示するには、
void print_tree(vector<vector<int>> &tree, int now, int prev, int depth) {
for (int i = 0; i < depth; i++) /* indent to show depth */
cout << " ";
cout << now << endl; /* print current node */
for (int next : tree[now]) {
if (next == prev) continue;
print_tree(tree, next, depth + 1); /* print child nodes */
}
}
二分木の場合は、子が最大2つなので、親の左右に表示できるが、一般的な木の場合は子が2つとは限らないため、一方に集めて表示した。根を0とした場合はこのように表示される。
0
2
1
5
6
3
4
木のDFS
木は、閉路がない＝親の方向に戻らないかぎり同じ頂点を通ることはない、ので次の頂点が親かどうかをチェックすればよい。
void dfs(vector<vector<int>> &tree, int u, int p) {
if (tree[u].size() == 1) { /* in case u is leaf */
;
return;
}
; /* pre-order traversal process */
for (int v : tree[u]) {
if (v == p) /* not return to parent */
continue;
dfs(tree, v, u);
}
; /* post-order traversal process */
}
木DP
DP（動的計画法）というと、ナップザック問題を例とした説明がよくある。DPというと、
- 次数が0, 1...nと増えていく
- nからn+1になるときの値の変化を漸化式で表すことができる
- 次数が0, 1のときの値からスタートして、nまで漸化式で計算することで、次数がnの値が求められる
という理解をしていた。
vector<vector<int>> dp(n+1, vector<int> (m, 0));
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
if (j >= w[i])
dp[i+1][j] = max(dp[i][j - w[i]] + v[i], dp[i+1][j]);
}
木におけるDPの遷移は、「次数がnからn+1に変化する」ではなく、「頂点uから次の頂点vに移動する」とすることになる。この頂点uから頂点vへの移動がグラフで与えられる。
木の高さ（＝根から最も遠い点までの距離）を求めるには、葉まで行って、そこから戻ってきながら高さを1ずつ増やしていくことで求められる。根を0とした場合の木の高さは2、
根を2にした場合の木の高さは3になる。
与えられるグラフは木であるので、無向グラフとして受け取り、グラフを辿るときに親方向に後戻りしないようにして木を辿っていく。
void dfs(vector<vector<int>> &graph, int u, int p, vector<int> &dp) {
if (graph[u].size() == 1) { /* in case u is leaf */
dp[u] = 0;
return;
}
int maxLength = 0;
for (int v : graph[u]) { /* next node */
if (v == p) continue; /* skip if node is parent */
dfs(graph, v, u, dp); /* goto DFS */
maxLength = max(dp[v], maxLength);
}
dp[u] = maxLength + 1; /* update dp[u] in post-order */
}
main()でグラフを入力し、関数dfs()を呼び出すことでdp[root]に木の高さが得られる。
int main() {
int n;
cin >> n;
vector<vector<int>> graph(n);
for (int i = 0; i < n-1; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<int> dp(n, 0);
int root = 0, parent = -1; /* set 0 as root, no parent */
dfs(graph, root, parent, dp);
cout << dp[root] << endl;
return 0;
}
ところで、根からの各頂点までの距離は、根から距離を増やしていく方法でも得られる。
void dfs(vector<vector<int>> &graph, int u, int p, vector<int> &dp) {
if (graph[u].size() == 1) {
return dp[u];
}
int maxLength = 0;
for (int v : graph[u]) { /* next node */
if (v == p) continue; /* skip if node is parent */
dp[v] = dp[u] + 1; /* update dp[v] in pre-order */
maxLength = max(dfs(graph, v, u, dp), maxLength); /* go to DFS */
}
return maxLength;
}
ここではDFSの行きかげで実装してみたが、BFSでも同じ結果が得られる。
木の高さを求める場合は、各頂点で、その前の頂点までの高さに+1していくので、行きがけでも帰りがけでもできるが、子頂点の個数を求めるような場合は、子の部分木の情報が必要になるので、帰りがけでdpを更新することになる。
実装してみると、このようになる。
void dfs(vector<vector<int>> &graph, int u, int p, vector<int> &dp) {
if (graph[u].size() == 1) { /* in case u is leaf */
dp[u] = 0;
return;
}
int childs = 0;
for (int v : graph[u]) {
if (v == p) continue; /* skip if v is parent */
dfs(graph, v, u, dp); /* go to DFS */
childs += dp[v] + 1; /* sum of v's child + v self */
}
dp[u] = childs; /* update dp[u] in post-order */
}