KruskyalとPrim最小生成樹java実現
5561 ワード
Kruskyal最小生成ツリー
// http://blog.csdn.net/luomingjun12315/article/details/47700237
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class KruskalMST {
private static int MAX = 100;
private ArrayList edge = new ArrayList();//
private ArrayList target = new ArrayList();// ,
private int[] parent = new int[MAX];//
private static double INFINITY = 99999999.99;//
private double mincost = 0.0;//
private int n;//
public static void main(String args[]){
KruskalMST sp = new KruskalMST();
sp.init();
sp.kruskal();
sp.print();
}
//
public void init(){
Scanner scan = new Scanner(System.in);
int p,q;
double w;
System.out.println("spanning tree begin!Input the node number:");
n = scan.nextInt();
System.out.println("Input the graph(-1,-1,-1 to exit)");
while(true){
p = scan.nextInt();
q = scan.nextInt();
w = scan.nextDouble();
if(p < 0 || q < 0 || w < 0){
break;
}
Edge e = new Edge();
e.start = p;
e.end = q;
e.cost = w;
edge.add(e);
}
mincost = 0.0;
for (int i = 1; i <= n; ++i){
parent[i] = i;
}
scan.close();
}
//
public void union(int j, int k){
for(int i = 1; i <= n; ++i){
if(parent[i] == j){
parent[i] = k;
}
}
}
//Kruskal
public void kruskal(){
// n-2
int i = 0;
while(i < n-1 && edge.size() > 0){
// ,
double min = INFINITY;
Edge tmp = null;
for(int j = 0; j < edge.size(); ++j){
Edge tt = edge.get(j);
if(tt.cost < min){
min = tt.cost;
tmp = tt;
}
}
int jj = parent[tmp.start];
int kk = parent[tmp.end];
// ,
if(jj != kk){
++i;
target.add(tmp);
mincost += tmp.cost;
union(jj,kk);
}
edge.remove(tmp);
}
if(i != n-1){
System.out.println("no spanning tree");
}
}
//
public void print(){
double sum = 0;
for(int i = 0; i < target.size(); ++i){
Edge e = target.get(i);
System.out.println("the " + (i+1) + "th edge:" + e.start + "---" + e.end + " cost:" + e.cost);
sum += e.cost;
}
System.out.println("the MST cost:"+sum);
}
}
class Edge
{
public int start;//
public int end;//
public double cost;//
}
Prim最小生成ツリー// http://blog.csdn.net/yeruby/article/details/38615045
import java.util.Scanner;
public class PrimMST {
private static int MAX = 100;
private static int[][] graph = new int[MAX][MAX];
private int[] lowcost = new int[MAX];//
private int[] mst = new int[MAX];//
private static int INFINITY = 99999999;//
private int mincost = 0;//
private static int mstcost = 0;//
private static int n;//
private int middle;//
private int sum = 0;
public static void main(String args[]) {
PrimMST sp = new PrimMST();
sp.init();
mstcost = sp.prim(graph, n);
System.out.println(" :" + mstcost);
}
//
public void init() {
Scanner scan = new Scanner(System.in);
int p, q, w;
System.out.println("spanning tree begin!Input the node number:");
n = scan.nextInt();
System.out.println("Input the graph(-1,-1,-1 to exit)");
while (true) {
p = scan.nextInt();
q = scan.nextInt();
w = scan.nextInt();
if (p < 0 || q < 0 || w < 0) {
break;
}
graph[p][q] = w;
graph[q][p] = w;
}
scan.close();
}
// prim
public int prim(int graph[][], int n) {
for (int i = 2; i <= n; i++) {
lowcost[i] = graph[1][i];
mst[i] = 1;
}
mst[1] = 0;
for (int i = 2; i <= n; i++) {
mincost = INFINITY;
middle = 0;
for (int j = 0; j <= n; j++) {
if (lowcost[j] < mincost && lowcost[j] != 0) {
mincost = lowcost[j];
middle = j;
}
}
System.out.println(mst[middle] + "--" + middle + "==" + mincost);
sum += mincost;
lowcost[middle] = 0;
for (int j = 0; j <= n; j++) {
if (graph[middle][j] < lowcost[j]) {
lowcost[j] = graph[middle][j];
mst[j] = middle;
}
}
}
return sum;
}
}