Java実装最小生成ツリーアルゴリズム(Primアルゴリズム)
8195 ワード
Primアルゴリズム
Primアルゴリズムは、成長中のツリーにエッジを追加します.最初はこの木には頂点が1つしかありませんでしたが、V-1のエッジが追加され、次の接続ツリーの頂点とツリーになく重みが最も小さいエッジがツリーに追加されます.
インプリメンテーション
最小生成ツリーの遅延実装最小生成ツリーのエッジ(横断エッジ)Queue mst を1つのキューで保存最小優先キューすべてのエッジMinPQ pqを保持最小エッジを削除することによって新しい最小生成ツリーのエッジが得られ、スタックベースの最小優先キューによって が実現される.すべての頂点を保持する配列(頂点がアクセスされているかどうかをマークするために使用され、1つのエッジに2つの頂点があり、2つの頂点がアクセスされていることは、追加されていることを示し、エッジが失効していることを示す) .
インプリメンテーション:まずvisit()メソッドで頂点をツリーに追加し、アクセス済みとしてマークします.次に、頂点に関連付けられたすべてのエッジを優先キューに追加して、キューにツリー頂点と非ツリー頂点を接続するすべてのエッジが含まれていることを保証します.
コード内ループ実装:優先キューからエッジを取り出してツリーに追加し、エッジの別の頂点をツリーに追加し、新しい頂点をパラメータとしてvisit()メソッドを呼び出して横断エッジの結合を更新します.すなわち、新しい頂点に関連付けられたエッジを優先キューに追加し、優先キューから重みが最小で失効していないエッジを取り出します.新しい頂点ループ呼び出しを再取得
重み付きエッジのデータ型Edge
加重無方向図のデータ型
最小優先キュー
テスト
実行結果:
Primアルゴリズムは、成長中のツリーにエッジを追加します.最初はこの木には頂点が1つしかありませんでしたが、V-1のエッジが追加され、次の接続ツリーの頂点とツリーになく重みが最も小さいエッジがツリーに追加されます.
インプリメンテーション
最小生成ツリーの遅延実装
インプリメンテーション:まずvisit()メソッドで頂点をツリーに追加し、アクセス済みとしてマークします.次に、頂点に関連付けられたすべてのエッジを優先キューに追加して、キューにツリー頂点と非ツリー頂点を接続するすべてのエッジが含まれていることを保証します.
コード内ループ実装:優先キューからエッジを取り出してツリーに追加し、エッジの別の頂点をツリーに追加し、新しい頂点をパラメータとしてvisit()メソッドを呼び出して横断エッジの結合を更新します.すなわち、新しい頂点に関連付けられたエッジを優先キューに追加し、優先キューから重みが最小で失効していないエッジを取り出します.新しい頂点ループ呼び出しを再取得
public class LazyPrimMST {
public boolean[] marked; //
public Queue mst; //
public MinPQ pq; // ( )
/**
* v v-1 v ，v
* @param G
*/
public LazyPrimMST(EdgeWeightGraph G) {
pq = new MinPQ();
mst = new LinkedList<>();
marked = new boolean[G.V()];
visit(G, 0);
while (!pq.isEmpty()) {
Edge e = pq.delMin();
System.out.println(" :"+e);
int v = e.either(),w = e.other(v);
if(marked[v]&&marked[w])
continue; //
System.out.println(" ："+e);
mst.add(e); //
System.out.println("------------------------------------");
if(!marked[v]) //
visit(G,v);
if(!marked[w])
visit(G,w);
}
}
/**
* @param g
* @param i
*/
private void visit(EdgeWeightGraph g, int v) {
// v v
marked[v] = true;
for(Edge e : g.adj(v)) {
if(!marked[e.other(v)])
System.out.println(" "+ e);
pq.insert(e);
}
}
public Iterable edges(){
return mst;
}
}
重み付きエッジのデータ型Edge
public class Edge implements Comparable{
public final int v;
public final int w;
public final double weight;
public Edge(int v,int w,double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public int either() {
return v;
}
public int other(int vertex) {
if(vertex==v)
return w;
else if(vertex==w)
return v;
else
throw new RuntimeException("Inconsistent Edge");
}
public double weight() {
return weight;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return String.format("%d-%d %.2f", v,w,weight);
}
/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
@Override
public int compareTo(Edge o) { // ComparaTo ，
// TODO Auto-generated method stub
if(this.weight()o.weight()) return 1;
else return 0;
}
}
加重無方向図のデータ型
public class EdgeWeightGraph {
private final int V;
private int E; //
private Bag[] adj; //
public EdgeWeightGraph(int v) {
this.V = v;
this.E = 0;
adj = new Bag[V];
for(int i = 0;i();
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}
public Iterable adj(int v){
return adj[v];
}
public Iterable edges(){ //
Stack s = new Stack();
for(int i = 0;i 最小優先キュー
public class MinPQ> {
private Key[] pq;
private int N = 0;
public MinPQ(int initCapacity) {
pq = (Key[]) new Comparable[initCapacity + 1];
}
public MinPQ() {
this(1);
}
public void insert(Key key) {
if (N == pq.length - 1) {
resize(2 * pq.length);
}
N++;
pq[N] = key;
swim(N);
}
/**
* @param i
*/
private void resize(int i) {
Key[] temp = (Key[]) new Comparable[i];
for (int j = 0; j < pq.length; j++) {
temp[j] = pq[j];
}
pq = temp;
}
public Key delMin() {
exch(pq, 1, N);
Key min = pq[N];
pq[N] = null;
N--;
skin(1);
return min;
}
private void swim(int i) {
while (i > 1 && greater(i / 2, i)) {
exch(i, i / 2);
i = i / 2;
}
}
private void exch(int i, int j) {
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
/**
* @param i
*/
private void skin(int i) {
while (2 * i <= N) {
int k = 2 * i;
if (k < N && greater(k, k + 1)) { //
k++;
}
if (greater(k, i)) { //
break;
}
exch(pq, i, k);
i = k;
}
}
private boolean greater(int i, int k) {
return pq[i].compareTo(pq[k]) > 0;
}
/**
* @param k
* @param i
*/
private static void exch(Comparable[] v, int k, int i) {
Comparable temp = v[i];
v[i] = v[k];
v[k] = temp;
}
public static void show(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
/**
* @param i
* @param k
* @return
*/
private static boolean greater(Comparable i, Comparable k) {
// TODO Auto-generated method stub
System.out.println(i + " " + k);
return i.compareTo(k) > 0;
}
public int size() {
return N;
}
public boolean isEmpty() {
if (N == 0) {
return true;
}
return false;
}
}
テスト
public class Test {
public static void main(String[] args) {
EdgeWeightGraph graph = new EdgeWeightGraph(8);
graph.addEdge(new Edge(4, 5, 0.35));
graph.addEdge(new Edge(4, 7, 0.37));
graph.addEdge(new Edge(5, 7, 0.28));
graph.addEdge(new Edge(0, 7, 0.16));
graph.addEdge(new Edge(1, 5, 0.32));
graph.addEdge(new Edge(0, 4, 0.38));
graph.addEdge(new Edge(2, 3, 0.17));
graph.addEdge(new Edge(1, 7, 0.19));
graph.addEdge(new Edge(0, 2, 0.26));
graph.addEdge(new Edge(1, 2, 0.36));
graph.addEdge(new Edge(1, 3, 0.29));
graph.addEdge(new Edge(2, 7, 0.34));
graph.addEdge(new Edge(6, 2, 0.40));
graph.addEdge(new Edge(3, 6, 0.52));
graph.addEdge(new Edge(6, 0, 0.58));
graph.addEdge(new Edge(6, 4, 0.93));
LazyPrimMST lpm = new LazyPrimMST(graph);
Queue q = new LinkedList();
q = (Queue) lpm.edges();
System.out.println(" ：");
for (Edge edge : q) {
System.out.println(edge);
}
}
}
実行結果:
6-0 0.58
0-2 0.26
0-4 0.38
0-7 0.16
:0-7 0.16
：0-7 0.16
------------------------------------
2-7 0.34
1-7 0.19
5-7 0.28
4-7 0.37
:0-7 0.16
:1-7 0.19
：1-7 0.19
------------------------------------
1-3 0.29
1-2 0.36
1-5 0.32
:1-7 0.19
:0-2 0.26
：0-2 0.26
------------------------------------
6-2 0.40
2-3 0.17
:2-3 0.17
：2-3 0.17
------------------------------------
3-6 0.52
:2-3 0.17
:0-2 0.26
:5-7 0.28
：5-7 0.28
------------------------------------
4-5 0.35
:5-7 0.28
:1-3 0.29
:1-3 0.29
:1-5 0.32
:1-5 0.32
:2-7 0.34
:2-7 0.34
:4-5 0.35
：4-5 0.35
------------------------------------
6-4 0.93
:4-5 0.35
:1-2 0.36
:1-2 0.36
:4-7 0.37
:4-7 0.37
:0-4 0.38
:0-4 0.38
:6-2 0.40
：6-2 0.40
------------------------------------
:6-2 0.40
:3-6 0.52
:3-6 0.52
:6-0 0.58
:6-0 0.58
:6-4 0.93
:6-4 0.93
：
0-7 0.16
1-7 0.19
0-2 0.26
2-3 0.17
5-7 0.28
4-5 0.35
6-2 0.40