プリム法の証明

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

プリム法とは

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

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

プリム法の証明

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

木Tが最小全域木の部分木であるとします。
木Tから、Tに含まれない頂点に対する辺の内、最もコストが小さい辺をe、その辺の結ぶ頂点の内Tに含まれない方をvとします。

操作2では木Tに辺eを追加します。これは、最小全域木に辺eが含まれるからです。
これを背理法で証明します。
最小全域木に辺eが含まれないと仮定します。
このとき、辺eを含まないある全域木Uが最小全域木だとします。

Uにはvが含まれているので、Uには「Tに含まれる頂点->(Tに含まれない頂点Xnが0個以上)->v」という辺eを使わない経路が存在します。（図の緑+黄色）
（しない場合は、vへの辺が無いことになるので、Uが全域木であることに矛盾します。）

この「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;
}