読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

最小全域木(minimum spanning tree)

リポジトリ

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

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

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

/** 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法

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

 X\subset Vに対する全域木 Tが定まっていて、 Tを部分グラフとして含むような VのMSTが存在するとき、
{ e = {\arg\min}_{\{ (u,v) | u\in X, v\in V-X \}} }を含む VのMSTで、 Tを部分グラフとするものが存在する。
(証明)
 Tを部分グラフとして含むような VのMSTに、 eが含まれないと仮定する。
これに、 eを加えると閉路ができる。
閉路に含まれる辺には、 \{f|f=(u',v')\neq e, u'\in X, v'\in V-X\} となる fが必ず存在する( w(f)>w(e))。
そこで、 Tを部分グラフとして含むような VのMSTから fを取り除いて、 eを加えることで全域木を作ることができ、合計コストが元のMSTの合計コストより小さくなり矛盾している。
従って、 eを含む VのMSTで、 Tを部分グラフとするものが存在する。

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

/**
 * 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); }