Prufer Code（木の符号化・復号）

tree/prufer_code.hpp · GitHub で見る

共通ページ

頂点番号が 0 始まりのラベル付き無向木と、Prufer 符号を相互に変換します。符号化では、番号が最小の葉を取り除き、その隣接頂点を記録します。

#include "lib/tree/prufer_code.hpp"

std::vector<std::vector<int>> graph{ {1}, {0, 2, 3}, {1}, {1} };
auto code = prufer_encode(graph); // {1, 1}
auto restored = prufer_decode(code);
auto singleton = prufer_decode({}, 1); // 頂点 0 だけの木

関数	内容・返り値	計算量
prufer_encode(graph)	無向木の隣接リストから vector<int> の符号を返す。入力は変更しない	\(O(n)\)
prufer_decode(code)	頂点数を code.size() + 2 とし、vector<vector<int>> の無向木を返す	\(O(n)\)
prufer_decode(code,n)	頂点数を明示して復号。0・1 頂点にも対応する	\(O(n)\)

graph[v] には頂点 v の隣接頂点を並べます。各辺は両方向にそれぞれ 1 回記録し、自己辺・多重辺のない連結な木を渡してください。隣接リストをソートする必要はありません。復号結果も各辺を両方向に持ち、隣接頂点の並び順は保証しません。往復変換では辺集合が一致します。

頂点数は INT_MAX 以下とします。\(n\geq2\) では符号の長さは \(n-2\)、各要素は [0,n) です。明示した n と符号の長さは一致させてください。不正なグラフ全般を検査するAPIではありません。

0・1・2 頂点の符号は、いずれも空配列です。prufer_decode({}) は 2 頂点を 1 辺で結んだ木を返します。0・1 頂点を復元する場合は prufer_decode({},0)・prufer_decode({},1) と頂点数を指定します。

頂点数を \(n\) として、符号化・復号はともに \(O(n)\) 時間、出力を含む \(O(n)\) 空間です。空の木は \(O(1)\) 時間・空間です。

コード

#ifndef PRUFER_CODE_HPP
#define PRUFER_CODE_HPP

#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

inline std::vector<int> prufer_encode(const std::vector<std::vector<int>> &graph) {
	assert(graph.size() <= std::size_t(std::numeric_limits<int>::max()));
	const int n = static_cast<int>(graph.size());
	std::vector<int> degree(n), adjacent(n);
	[[maybe_unused]] std::size_t edges = 0;
	for (int v = 0; v < n; ++v) {
		assert(graph[v].size() < std::size_t(n));
		degree[v] = static_cast<int>(graph[v].size());
		edges += graph[v].size();
		for (int u : graph[v]) {
			assert(0 <= u && u < n && u != v);
			adjacent[v] ^= u;
		}
	}
	assert(edges == (n ? std::size_t(n - 1) * 2 : 0));
	if (n <= 2) return {};
	std::vector<int> code;
	code.reserve(n - 2);
	int next = 0;
	while (next < n && degree[next] != 1) ++next;
	int leaf = next;
	for (int i = 0; i < n - 2; ++i) {
		assert(leaf < n && degree[leaf] == 1);
		const int parent = adjacent[leaf];
		assert(0 <= parent && parent < n && degree[parent] > 0);
		code.push_back(parent);
		degree[leaf] = 0;
		adjacent[parent] ^= leaf;
		if (--degree[parent] == 1 && parent < next) leaf = parent;
		else {
			do { ++next; } while (next < n && degree[next] != 1);
			leaf = next;
		}
	}
	return code;
}

inline std::vector<std::vector<int>> prufer_decode(const std::vector<int> &code, int n) {
	assert(n >= 0 && code.size() == (n >= 2 ? std::size_t(n - 2) : 0));
	std::vector<std::vector<int>> graph(n);
	if (n <= 1) return graph;
	std::vector<int> degree(n, 1);
	for (int v : code) {
		assert(0 <= v && v < n);
		++degree[v];
	}
	for (int v = 0; v < n; ++v) graph[v].reserve(degree[v]);
	int next = 0;
	while (degree[next] != 1) ++next;
	int leaf = next;
	for (int parent : code) {
		graph[leaf].push_back(parent);
		graph[parent].push_back(leaf);
		degree[leaf] = 0;
		if (--degree[parent] == 1 && parent < next) leaf = parent;
		else {
			do { ++next; } while (degree[next] != 1);
			leaf = next;
		}
	}
	graph[leaf].push_back(n - 1);
	graph[n - 1].push_back(leaf);
	return graph;
}

inline std::vector<std::vector<int>> prufer_decode(const std::vector<int> &code) {
	assert(code.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
	return prufer_decode(code, static_cast<int>(code.size()) + 2);
}

#endif

Back to top page