Kruskal`s algorithm
概述
- 克魯斯卡爾算法(Kruskal`s algorithm)也是求最小生成樹的算法, 也就是在包含 n個頂點的帶權無向連通圖中, 找出(n-1)條邊的最小耗費生成樹(Minimum Cost Spanning Tree), 簡稱 MST
- 克魯斯卡爾算法的時間複雜度為 O(eloge) e為網中的邊數
- 基本思想: 将所有的邊, 按照權值從小到大進行排序, 并保證邊的終點不構成回路(指每個邊的終點不允許重合)
公交站問題
- 某城市有7個居民區(A,B,C,D,E,F,G), 需要在各區建一個公交站點連通. 各個村莊的距離用邊線權值來表示, 比如 A-B距離12公裡
- 需要保證各個區都能連通, 且連通的總裡程為最短
算法-最小生成樹算法(克魯斯卡爾算法 Kruskal`s algorithm)概述 
算法-最小生成樹算法(克魯斯卡爾算法 Kruskal`s algorithm)概述 public class KruskalAlgorithmApp {
/** 邊的總個數*/
private int edgeCount;
/** 頂點數組*/
private char[] vertexes;
/** 鄰接矩陣*/
private int[][] matrix;
/** 定義常量, 9999表示某頂點間不連通*/
private static final int INF = 9999;
public static void main(String[] args) {
char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
/** 設定鄰接矩陣的頂點與頂點間的邊(附帶權值)*/
int matrix[][] = {
/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ { 0, 12, INF, INF, INF, 16, 14},
/*B*/ { 12, 0, 10, INF, INF, 7, INF},
/*C*/ { INF, 10, 0, 3, 5, 6, INF},
/*D*/ { INF, INF, 3, 0, 4, INF, INF},
/*E*/ { INF, INF, 5, 4, 0, 2, 8},
/*F*/ { 16, 7, 6, INF, 2, 0, 9},
/*G*/ { 14, INF, INF, INF, 8, 9, 0}
};
KruskalAlgorithmApp mst = new KruskalAlgorithmApp(vertexes, matrix);
/** 列印鄰接矩陣*/
mst.print();
/** 求出最小生成樹*/
mst.kruskal();
}
/** 定義邊類(一個執行個體表示一條邊)*/
class Edge {
/** 指定邊的第1個頂點*/
char start;
/** 指定邊的第2個頂點*/
char end;
/** 指定邊的權值*/
int weight;
public Edge(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "Edge [<" + start + "," + end + ">=" + weight + "]";
}
}
public KruskalAlgorithmApp(char[] vertexes, int[][] matrix) {
/** 初始化頂點個數*/
int vertexCount = vertexes.length;
/** 初始化頂點*/
this.vertexes = new char[vertexCount];
for(int i = 0; i < vertexCount; i++) {
this.vertexes[i] = vertexes[i];
}
/**初始化邊*/
this.matrix = new int[vertexCount][vertexCount];
for(int i = 0; i < vertexCount; i++) {
for(int j= 0; j < vertexCount; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
/** 統計邊的條數*/
for(int i =0; i < vertexCount; i++) {
for(int j = i+1; j < vertexCount; j++) {
if(this.matrix[i][j] != INF) {
edgeCount++;
}
}
}
}
/** 列印鄰接矩陣*/
public void print() {
System.out.println("鄰接矩陣為:");
for(int i = 0; i < vertexes.length; i++) {
for(int j = 0; j < vertexes.length; j++) {
System.out.printf("%6d", matrix[i][j]);
}
System.out.println();
}
}
/** 通過冒泡排序算法将邊從小到大排序*/
private void sortEdges(Edge[] edges) {
for(int i = 0; i < edges.length - 1; i++) {
for(int j = 0; j < edges.length - 1 - i; j++) {
if(edges[j].weight > edges[j+1].weight) {
Edge tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
/** 查找頂點傳回對應下标*/
private int getPosition(char ch) {
for(int i = 0; i < vertexes.length; i++) {
if(vertexes[i] == ch) {
return i;
}
}
return -1;
}
/** 擷取鄰接矩陣中的所有有效邊*/
private Edge[] getEdges() {
int index = 0;
Edge[] edges = new Edge[edgeCount];
for(int i = 0; i < vertexes.length; i++) {
for(int j = i+1; j <vertexes.length; j++) {
if(matrix[i][j] != INF) {
edges[index++] = new Edge(vertexes[i], vertexes[j], matrix[i][j]);
}
}
}
return edges;
}
/** 擷取下标為 i的頂點的終點, 用于判斷後面兩個頂點的終點是否相同
* @param ends: 此參記錄了各個頂點對應的終點, ends是在周遊過程中, 逐漸形成的
* @param i: 表示傳入的頂點對應的下标
* @return 傳回下标 i頂點對應的終點的下标*/
private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
while(ends[i] != 0) { /** 非等于0, 意思為 i(頂點下标)有對應的終點的下标*/
i = ends[i];
}
return i;
}
/** 求出最小生成樹*/
public void kruskal() {
/** 鄰接矩陣中的所有有效邊*/
Edge[] edges = getEdges();
System.out.println("鄰接矩陣中的所有有效邊: " + Arrays.toString(edges) + " 共"+ edges.length);
/** 将邊從小到大排序*/
sortEdges(edges);
/** 最終結果最小生成樹*/
Edge[] result = new Edge[edgeCount];
/** 最終結果最小生成樹的索引*/
int index = 0;
/** 儲存`已有最小生成樹`的每個頂點在最小生成樹中的終點*/
int[] ends = new int[edgeCount];
/** 周遊鄰接矩陣中的所有有效邊*/
for(int i = 0; i < edgeCount; i++) {
/** 擷取第 i條邊的第1個頂點下标*/
int p1 = getPosition(edges[i].start); // p1=4
/** 擷取第 i條邊的第2個頂點下标*/
int p2 = getPosition(edges[i].end); // p2=5
/** 擷取 p1頂點下标在已有最小生成樹中的終點*/
int m = getEnd(ends, p1); // m=4
/** 擷取 p2頂點下标在已有最小生成樹中的終點*/
int n = getEnd(ends, p2); // n=5
/** 判斷是否構成回路*/
if(m != n) { /** 沒有構成回路*/
/** m(p1的終點下标)設定為`已有最小生成樹 ends`的下标, 再将 n(p2的終點下标) 作為對應值儲存<E,F> [0,0,0,0,5,0,0,0,0,0,0,0]*/
ends[m] = n;
/** 将第 i條有效邊加到結果數組中*/
result[index++] = edges[i];
}
}
System.out.println("最小生成樹為:");
for(int i = 0; i < index; i++) {
System.out.println(result[i]);
}
}
}
輸出:
鄰接矩陣為:
0 12 9999 9999 9999 16 14
12 0 10 9999 9999 7 9999
9999 10 0 3 5 6 9999
9999 9999 3 0 4 9999 9999
9999 9999 5 4 0 2 8
16 7 6 9999 2 0 9
14 9999 9999 9999 8 9 0
鄰接矩陣中的所有有效邊: [Edge [<A,B>=12], Edge [<A,F>=16], Edge [<A,G>=14], Edge [<B,C>=10], Edge [<B,F>=7], Edge [<C,D>=3], Edge [<C,E>=5], Edge [<C,F>=6], Edge [<D,E>=4], Edge [<E,F>=2], Edge [<E,G>=8], Edge [<F,G>=9]] 共12
最小生成樹為:
Edge [<E,F>=2]
Edge [<C,D>=3]
Edge [<D,E>=4]
Edge [<B,F>=7]
Edge [<E,G>=8]
Edge [<A,B>=12]
如果您覺得有幫助，歡迎點贊哦 ~ 謝謝!!
