最小全域木(minimum spanning tree)

リポジトリ

• 全域木(spanning tree), 極大木 :

においてとなる辺集合があるとき、グラフが木（閉路を持たないグラフ）であるなら、 をの全域木と呼ぶ。
(全域木が存在することと連結であることは同値)

• 最小全域木(MST: Minimum Spanning Tree) :

使われる辺のコストの和を最小にする全域木。
最小全域木問題の性質上、最短路問題のように、負の辺を気にする必要は無いはず。

/** Result of Minimum Spanning Tree Algorithm */
public static class MSTResult{
	private int totalCost;
	private List<Edge> edgeList;
	public MSTResult(int totalCost, List<Edge> edgeList){ this.totalCost = totalCost; this.edgeList = edgeList; }
	public final int getTotalCost(){ return totalCost; }
	public final List<Edge> getEdgeList(){ return edgeList; }
}

Prim法

無向グラフにおける最小全域木を求めるアルゴリズムの一つ。
まず、１つの頂点のみからなる木を考える。
ここから、グリーディにとその他の頂点を結ぶ最小コストの辺をに付け加えることを繰り返して、全域木を作る。基本的にはDijkstra法と同じなので、。

に対する全域木が定まっていて、を部分グラフとして含むようなのMSTが存在するとき、
を含むのMSTで、を部分グラフとするものが存在する。
(証明)
を部分グラフとして含むようなのMSTに、が含まれないと仮定する。
これに、を加えると閉路ができる。
閉路に含まれる辺には、となるが必ず存在する()。
そこで、を部分グラフとして含むようなのMSTからを取り除いて、を加えることで全域木を作ることができ、合計コストが元のMSTの合計コストより小さくなり矛盾している。
従って、を含むのMSTで、を部分グラフとするものが存在する。

このことから、Prim法で、にをとなるまで付け加えていくことにより、の最小全域木が求まる。

/**
 * Calculates total edge cost and edge list of minimum spanning tree via Prim's algorithm O(|E|log|V|).<br>
 * @param adjList adjacency list (※edge weights can be negative)
 * @param s	  source node
 * @return	  MSTResult
 */
public static MSTResult Prim(List<List<Edge>> adjList, int s) {
	int n = adjList.size(), totalCost = 0;
	List<Edge> T = new LinkedList<Edge>();
	boolean[] visited = new boolean[n];

	PriorityQueue<Edge> q = new PriorityQueue<Edge>();
	q.add( new Edge(-1, s, 0) );
	while(!q.isEmpty()){
		Edge e = q.poll();
		if(visited[e.d]) continue;
		T.add(e);
		totalCost += e.w;
		visited[e.d] = true;
		for(Edge f: adjList.get(e.d)) if(!visited[f.d]) q.add(f);
	}
	return new MSTResult(totalCost, T);
}
/**
 * Calculates total edge cost and edge list of minimum spanning tree via Prim's algorithm O(|E|log|V|)<br>
 * AOJ No. 0072
 * @param adjList adjacency list (※edge weights can be negative)
 * @return	MSTResult
 */
public static MSTResult Prim(List<List<Edge>> list){ return Prim(list, 0); }