プリム法の証明

かなり乱暴なことをしている気がします。厳密な証明は他をあたってください。

プリム法とは

最小全域木を構成するアルゴリズムの一つです。
以下の手順で行います。

  1. ある頂点を選び、木Tに追加します
  2. 木Tから最も近い頂点を木Tに追加します
  3. Tが全域木になるまで2を繰り返します
  4. Tは最小全域木です

プリム法の証明

1が終わった段階で、木Tは頂点を一つ含む木です。このとき明らかに、木Tは最小全域木の部分木です。

木Tが最小全域木の部分木であるとします。
木Tから、Tに含まれない頂点に対する辺の内、最もコストが小さい辺をe、その辺の結ぶ頂点の内Tに含まれない方をvとします。
f:id:eiya5498513:20170830211615p:plain
操作2では木Tに辺eを追加します。これは、最小全域木に辺eが含まれるからです。
これを背理法で証明します。
最小全域木に辺eが含まれないと仮定します。
このとき、辺eを含まないある全域木をUが最小全域木だとします。
f:id:eiya5498513:20170830210508p:plain
Uにはvが含まれているので、Uには「Tに含まれる頂点->(Tに含まれない頂点Xnが0個以上)->v」という辺eを使わない経路が存在します。(図の緑+黄色)
(しない場合は、vへの辺が無いことになるので、Uが全域木であることに矛盾します。)
f:id:eiya5498513:20170830211352p:plain
この「Tに含まれる頂点->X1(又はv)」の辺をfとします。
最小全域木からfを取り除いて、eを追加した木は、明らかに全域木です。
又、この全域木は、Uよりもコストの合計が低いです。
これは、Uが最小全域木であるので矛盾します。
よって、「最小全域木に辺eが含まれない」という仮定は誤りです。
よって、最小全域木に辺eが含まれます。
よって、木Tに辺eを追加した木も最小全域木の部分木です。

おまけ

O(V^2)プリム法のコード(ほぼ蟻本のコピペ)

int cost[MAX_V][MAX_V]; // cost[u][v]は辺e=(u,v)のコスト(存在しない場合はINF)
int mincost[MAX_V]; // 集合Xからの辺の最小コスト
bool used[MAX_V]; // 頂点iがXに含まれているか
int V; // 頂点数
int prim() {
	for (int i = 0; i < V; ++i) {
		mincost[i] = INF;
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;
	while (true) {
		int v = -1;
		// Xに属さない頂点のうちXからの辺のコストが最小になる頂点を探す
		for (int u = 0; u < V; u++) {
			if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
		}
		if (v == -1) break;
		used[v] = true; // 頂点vをXに追加
		res += mincost[v]; // 辺のコストを加える
		for (int u = 0; u < V; u++) {
			mincost[u] = std::min(mincost[u], cost[v][u]);
		}
	}
	return res;
}

O(ElogE)プリム法(自作)
O(ElogV)が存在するはずなので、誰か教えてください...
恐らく、二重辺を認めないor消去して、O(ElogE)→O(Elog(V^2))→O(ElogV)とやると思われる。(Luzhiledプロありがとうございます)

#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <algorithm>
#include <iterator>

using COST_T = uint32_t;
constexpr uint32_t MAX_V = 変える;
constexpr COST_T INF = 変える;//std::numeric_limits<double>::infinity()

#if defined(_MSC_VER) && defined(_DEBUG)
static_assert(false, "リリースでコンパイルしないと遅いよ!!");
#endif

struct edge {
	uint32_t to;
	COST_T cost;
	edge() {}
	edge(uint32_t to_, COST_T cost_)
		:to(to_), cost(cost_) {}
};
std::vector<edge> graph[MAX_V];// 頂点vからの辺はgraph[v]
//O(V+ElogE)
COST_T prim(uint32_t s = 0) {
	static bool used[MAX_V]; // 頂点iがTに含まれているか
	for (int i = 0; i < MAX_V; ++i) {
		used[i] = false;
	}
	using Pair = std::pair<COST_T, uint32_t>;
	std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> queue;
	queue.emplace(0, s);
	COST_T res = 0;
	while (!queue.empty()) {
		// Tからの辺のコストが最小になる頂点
		COST_T cost = queue.top().first;
		uint32_t v = queue.top().second; queue.pop();
		if (used[v]) { continue; }

		used[v] = true; // 頂点vをTに追加
		res += cost; // 辺のコストを加える
		for (auto& next : graph[v]) {
			if (used[next.to]) { continue; }
			queue.emplace(next.cost, next.to);
		}
	}
	return res;
}