算法导论-java实现-最小生成树 MinimumSpanningTree，prim ，kruskal,次最小生成树SecondMinimumSpanningTree

package graph;

import java.awt.List;

import datastructure.Queue;

class Edge {
public int v;
public int u;
public int w;

public Edge(int v, int u, int w) {
this.v = v;
this.u = u;
this.w = w;
}
}

public class SpanningTree {
public int[][] G;
public int[][] maxTable;
public int num;
public int max;

public static void main(String args[]) {
new SpanningTree();
}

public SpanningTree() {
num = 9;
max = 1000;
G = new int[num][num];
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
G[i][j] = max;
}
}

G[0][1] = 4;
G[1][0] = 4;
G[0][7] = 8;
G[7][0] = 8;
G[1][7] = 11;
G[7][1] = 11;
G[7][8] = 7;
G[8][7] = 7;
G[6][7] = 1;
G[7][6] = 1;
G[1][2] = 8;
G[2][1] = 8;
G[2][8] = 2;
G[8][2] = 2;
G[6][8] = 6;
G[8][6] = 6;
G[2][3] = 7;
G[3][2] = 7;
G[2][5] = 4;
G[5][2] = 4;
G[5][6] = 2;
G[6][5] = 2;
G[3][5] = 14;
G[5][3] = 14;
G[3][4] = 9;
G[4][3] = 9;
G[4][5] = 10;
G[5][4] = 10;
//printGraphMatrix(MST_KRUUSKAL(G));

//printGraphMatrix(MST_PRIM(G));
printGraphMatrix(SMST(G));
//BFS(G);

}

public int[][] MST_PRIM(int[][] G) {
int[] key = new int[num];
int[] pi = new int[num];
int[] U = new int[num];
for (int i = 0; i < num; i++) {
key[i] = max;
pi[i] = max;
U[i] = i;
}
key[0] = -1;
int u;
// Queue Q=new Queue(1000);
MinHeapByKey Q = new MinHeapByKey(pi, key, U);
Q.display();
// for(int i=0;i<num;i++){
// Q.enQueue(i);
// }
while (!Q.empty()) {
u = Q.HeapExtractMin();

System.out.println("取出" + u);
for (int v = 0; v < num; v++) {
if (G[u][v] != max) {
if (Q.contain(v) && G[u][v] < Q.getKey(v)) {
// System.out.println(v+"被改动");
pi[v] = u;
// key[v]=G[u][v];
Q.changeKey(v, G[u][v]);
Q.display();
}
}
}
}
int index = 0;
for (int i = 1; i < pi.length; i++) {
System.out.println(i + " " + pi[i]);
}
int[][] A = new int[num][num];
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
boolean hasEdge = false;
A[i][j] = G[i][j];
for (int k = 0; k < num; k++) {
if (pi[k] == i && k == j || pi[k] == j && k == i) {
hasEdge = true;
}
}
if (hasEdge == false) {
A[i][j] = max;
A[j][i] = max;
}
}
}
return A;
}

public void BFS(int[][]G){
Queue Q = new Queue(1000);
Queue QQ = new Queue(1000);
Q.enQueue(0);
QQ.enQueue(0);
int x;
while(!Q.empty()) {
x = Q.deQueue();
System.out.println("便利到"+x);
for (int i = 0; i < num; i++) {
if (G[x][i] != max && !QQ.contains(i)) {
// search
Q.enQueue(i);
QQ.enQueue(i);

}
}
}
}
public int[][] SMST(int[][] G) {
int[][] A = MST_PRIM(G);
BFSFillMax(A);
boolean isFinish = false;
int rx, ry;
System.out.println("进入SMST");
for (int u = 0; u < num; u++) {
for (int v = 0; v < num; v++) {
if (A[u][v] == max && G[u][v]!=max) {
//uv有可能加入T'中，去掉xy
// 找出xy为uv上的max，看是否属于A
// 对G搜索，如果uv上的max--xy在A上，那么就选uv
Queue Q = new Queue(1000);
Queue QQ = new Queue(1000);
Q.enQueue(u);
QQ.enQueue(u);
int x;
do {
x = Q.deQueue();
for (int i = 0; i < num; i++) {
if (A[x][i] != max && !QQ.contains(i)) {
// search
if (maxTable[u][v] == A[x][i]) {
isFinish = true;
A[x][i] = max;
A[u][v] = G[u][v];
return A;
}
Q.enQueue(i);
QQ.enQueue(i);

}
System.out.println("走到了" + x);
}
} while (x == v);
}
}
}
return A;
}

public int[][] MST_KRUUSKAL(int[][] G) {
int[][] A = new int[num][num];
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
A[i][j] = 1000;
}
}
int[] vSet = new int[num];
for (int i = 0; i < num; i++) {
vSet[i] = i;
}
int edgeNum = 0;
for (int i = 0; i < num; i++) {
for (int j = i; j < num; j++) {
if (G[i][j] != max)
edgeNum++;
}
}
edgeNum = edgeNum;
// System.out.println(edgeNum);
Edge[] E = new Edge[edgeNum];
int index = 0;
for (int i = 0; i < num; i++) {
for (int j = i; j < num; j++) {
if (G[i][j] != max)
E[index++] = new Edge(i, j, G[i][j]);
}
}
Edge temp;
for (int i = 0; i < edgeNum; i++) {
for (int j = edgeNum - 1; j > i; j--) {
if (E[j].w < E[j - 1].w) {
temp = E[j - 1];
E[j - 1] = E[j];
E[j] = temp;
}
}
}
/*
* for(int i=0;i<edgeNum;i++){ System.out.print(" "+E[i].w); }
*/
int u, v, w;
for (int i = 0; i < edgeNum; i++) {
u = E[i].u;
v = E[i].v;
w = E[i].w;
if (vSet[u] != vSet[v]) {
A[u][v] = E[i].w;
A[v][u] = E[i].w;
for (int j = 0; j < vSet.length; j++) {
if (vSet[j] == vSet[u])
vSet[j] = vSet[v];
}
}
}
return A;
}

public void printGraphMatrix(int[][] ks) {
for (int i = 0; i < ks.length; i++) {
for (int j = 0; j < ks[i].length; j++) {
if (ks[i][j] != max)
System.out.print(ks[i][j] + " ");
else
System.out.print(" . ");
}
System.out.println();
}
}

public void BFSFillMax(int[][] A) {
maxTable = new int[num][num];
for (int u = 0; u < num; u++) {
for (int v = 0; v < num; v++) {
maxTable[u][v] = -1;
}
Queue Q = new Queue(1000);
Q.enQueue(u);
int x;
while (!Q.empty()) {
x = Q.deQueue();
// System.out.println(x);
for (int v = 0; v < num; v++) {
if (A[v][x] != max) {
if (maxTable[u][v] == -1 && u != v) {
if (x == u || A[x][v] > maxTable[u][x]) {
maxTable[u][v] = A[x][v];
} else {
maxTable[u][v] = maxTable[u][x];
}
Q.enQueue(v);
}
}
}
}
}
for (int i = 0; i < maxTable.length; i++) {
for (int j = 0; j < maxTable[i].length; j++) {
System.out.println(i + "和" + j + "之间的max是 " + maxTable[i][j]);
}
// System.out.println();
}
}
}