概念
- 圖的生成樹(shù)是圖的子圖戏锹，并且不形成環(huán)路
- 最小生成樹(shù)是帶權(quán)圖中所有生成樹(shù)里邊權(quán)值總和最小的一個(gè)解，可能不唯一
算法思路
- 將圖的所有邊按權(quán)重排序
- 按順序取出每條邊
- 按原位置拼接，如果形成環(huán)就跳過(guò)這一條邊的拼接
算法實(shí)現(xiàn)
圖的實(shí)現(xiàn)
- 此實(shí)現(xiàn)方法沒(méi)有節(jié)點(diǎn)類(lèi)
- 采用鄰接矩陣和頂點(diǎn)索引
- 邊類(lèi)有兩個(gè)成員變量，用于記錄兩個(gè)端點(diǎn)的索引
int A，int B - 鄰接矩陣
int[][] matrix(鄰接矩陣無(wú)需設(shè)置為沿對(duì)角線(xiàn)對(duì)稱(chēng))-
matrix[i][j]表示從索引i的節(jié)點(diǎn)指向索引j的節(jié)點(diǎn)的權(quán)值 - 權(quán)值為0表示兩點(diǎn)不連接或者自身與自身不連接
-
public class Graph<T> {
private int N; // N個(gè)節(jié)點(diǎn)
public int[][] matrix; // 鄰接矩陣
private T[] datas; // 保存每個(gè)節(jié)點(diǎn)的數(shù)據(jù)
public List<Edge> edges = new ArrayList<>();
class Edge {
int A; // 頂點(diǎn)索引
int B; // 頂點(diǎn)索引
public Edge(int a, int b) {
A = a;
B = b;
}
@Override
public String toString() {
return "<" +
datas[A] +
"-" + matrix[A][B] + "-" + datas[B] +
'>';
}
}
}
兩個(gè)重點(diǎn)
- 每條邊按權(quán)重排序
-
edges是圖所有邊的集合 - 需要重寫(xiě)
compare()方法窗市，默認(rèn)是升序排序 -
o1和o2是兩個(gè)對(duì)象也即兩條邊，return matrix[o1.A][o1.B] - matrix[o2.A][o2.B]的作用是饮笛，集合調(diào)用sort()方法進(jìn)行排序時(shí)咨察，按前一條邊的權(quán)重減去后一條邊的權(quán)重，小于0(前一條邊的權(quán)重小)則兩條邊的位置不變福青，大于0則交換位置(大概意思是這樣)
-
edges.sort(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
}
});
- 判斷是否有環(huán)(回路)
- 基本思路：判斷一條邊加入的時(shí)候兩個(gè)端點(diǎn)的 "終點(diǎn)" 是否相同扎拣，相同則說(shuō)明有環(huán)
-
getEnd()-
int[] ends保存所有節(jié)點(diǎn)的終點(diǎn)索引，但不是一開(kāi)始就確定，而是執(zhí)行最小生成樹(shù)算法的過(guò)程中才動(dòng)態(tài)確定每個(gè)元素的一個(gè)數(shù)組 - 最開(kāi)始
ends所有元素都是0 - 如果傳進(jìn)來(lái)的索引
i二蓝，ends[i] == 0則說(shuō)明這個(gè)節(jié)點(diǎn)是第一次被訪(fǎng)問(wèn)到誉券，則直接返回自身i(因?yàn)椴粫?huì)進(jìn)入循環(huán))，表示此節(jié)點(diǎn)的終點(diǎn)是自己 - 傳進(jìn)來(lái)索引
i刊愚，ends[i] != 0則說(shuō)明這個(gè)節(jié)點(diǎn)不是第一次被訪(fǎng)問(wèn)到踊跟，則把這個(gè)節(jié)點(diǎn)的終點(diǎn)索引賦值給i，如果ends[i]仍然不為0則說(shuō)明最開(kāi)始索引i的終點(diǎn)也有終點(diǎn)鸥诽，則再把終點(diǎn)的終點(diǎn)索引賦值給i商玫，while (ends[i] != 0)的作用就是不斷往下找到真正的終點(diǎn)
-
- 在遍歷邊集合過(guò)程中，
endOfA != endOfB如果邊的兩個(gè)端點(diǎn)的終點(diǎn)索引不同牡借，ends[endOfA] = endOfB;則把第一個(gè)端點(diǎn)的終點(diǎn)的終點(diǎn)設(shè)置為第二個(gè)端點(diǎn)的終點(diǎn)(可能有點(diǎn)繞拳昌，這步驟的原因是兩個(gè)端點(diǎn)終點(diǎn)不同，所以可以加入最終結(jié)果的邊集合钠龙，也就是這條邊已經(jīng)確定加入圖中炬藤，所以第一個(gè)端點(diǎn)必定能按這條邊到達(dá)第二個(gè)端點(diǎn)的終點(diǎn))
/**
* 本方法獲取索引為i的頂點(diǎn)的終點(diǎn), 用于判斷兩個(gè)頂點(diǎn)的終點(diǎn)是否相同
*
* @param ends 記錄各個(gè)頂點(diǎn)的終點(diǎn)(遍歷過(guò)程中才動(dòng)態(tài)確定的數(shù)組)
* @param i 傳入的頂點(diǎn)索引
* @return int 傳入索引對(duì)應(yīng)頂點(diǎn)的終點(diǎn)索引
*/
private int getEnd(int[] ends, int i) {
while (ends[i] != 0) { // 循環(huán)是為了找到最終的終點(diǎn)
i = ends[i];
}
return i;
}
/*****下面的代碼在最小生成樹(shù)算法主體方法中***********************/
// 如果這條邊取出來(lái)拼接后構(gòu)成環(huán), 則取消拼接操作
int endOfA = getEnd(ends, edge.A);
int endOfB = getEnd(ends, edge.B);
// 如果邊的第一個(gè)頂點(diǎn)的終點(diǎn)不等于第二個(gè)頂點(diǎn)的終點(diǎn)
if (endOfA != endOfB) {
// 設(shè)置第一個(gè)頂點(diǎn)的終點(diǎn)的終點(diǎn)為第二個(gè)頂點(diǎn)的終點(diǎn)
ends[endOfA] = endOfB;
result.add(edge); // 最小生成樹(shù)結(jié)果的邊集合
}
算法主體方法
-
int[] ends保存取出各個(gè)邊后依次拼接時(shí), 各個(gè)頂點(diǎn)的終點(diǎn)索引 - 把邊的權(quán)重排序
-
List<Edge> result保存最終結(jié)果的所有邊的集合 - 依次取出，不形成回路則拼接
- 將結(jié)果集合的所有邊以鄰接矩陣
int[][] treeMatrix的形式表現(xiàn)
/**
* 克魯斯卡爾算法-最小生成樹(shù)
*
* @return void
*/
public void KruskalTree() {
// ends保存取出各個(gè)邊后依次拼接時(shí), 各個(gè)頂點(diǎn)的終點(diǎn)索引
int[] ends = new int[N];
// 把邊的權(quán)重排序
edges.sort(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
}
});
// 保存最終結(jié)果的所有邊的集合
List<Edge> result = new ArrayList<>();
// 依次取出并拼接
for (Edge edge : edges) {
// 如果這條邊取出來(lái)拼接后構(gòu)成環(huán), 則取消拼接操作
int endOfA = getEnd(ends, edge.A);
int endOfB = getEnd(ends, edge.B);
// 如果邊的第一個(gè)頂點(diǎn)的終點(diǎn)不等于第二個(gè)頂點(diǎn)的終點(diǎn)
if (endOfA != endOfB) {
// 設(shè)置第一個(gè)頂點(diǎn)的終點(diǎn)的終點(diǎn)為第二個(gè)頂點(diǎn)的終點(diǎn)
ends[endOfA] = endOfB;
result.add(edge);
}
}
// 查看一下結(jié)果
System.out.println(result);
// 返回最小生成樹(shù)的鄰接矩陣
int[][] treeMatrix = new int[N][N];
// 將結(jié)果集合的所有邊以鄰接矩陣的形式表現(xiàn)
for (Edge edge : result) {
treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
}
System.out.println("最小生成樹(shù)的鄰接矩陣: ");
for (int[] nums : treeMatrix) {
System.out.println(Arrays.toString(nums));
}
}
測(cè)試
- 6個(gè)節(jié)點(diǎn)碴里，對(duì)應(yīng)保存數(shù)據(jù)為字母ABCDEF
-
int[][] set是為了初始化鄰接矩陣graph.setMatrix(set[i][0], set[i][1], set[i][2]) - 設(shè)置邊集合
graph.setEdges() - 執(zhí)行算法
graph.KruskalTree()
public static void main(String[] args) {
Graph<String> graph = new Graph<>(6);
graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F"});
// {端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值}
int[][] set = {{0, 1, 1},
{0, 2, 3},
{1, 3, 2},
{1, 5, 2},
{2, 3, 4},
{2, 5, 7},
{3, 4, 1},
{4, 5, 8}};
for (int i = 0; i < set.length; i++) {
// graph.setMatrix(端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值)
graph.setMatrix(set[i][0], set[i][1], set[i][2]);
}
graph.setEdges();
graph.KruskalTree();
}
測(cè)試結(jié)果
圖
最小生成樹(shù)
輸出結(jié)果如下
[<A-1-B>, <D-1-E>, <B-2-D>, <B-2-F>, <A-3-C>]
最小生成樹(shù)的鄰接矩陣:
[0, 1, 3, 0, 0, 0]
[0, 0, 0, 2, 0, 2]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
完整代碼實(shí)現(xiàn)
public class Graph<T> {
private int N; // 節(jié)點(diǎn)個(gè)數(shù)
public int[][] matrix; // 鄰接矩陣
private T[] datas; // 保存每個(gè)節(jié)點(diǎn)的數(shù)據(jù)
public List<Edge> edges = new ArrayList<>(); // 邊集合
class Edge {
int A; // 頂點(diǎn)索引
int B; // 頂點(diǎn)索引
public Edge(int a, int b) {
A = a;
B = b;
}
// 重寫(xiě)toString()方法方便查看結(jié)果
@Override
public String toString() {
return "<" +
datas[A] +
"-" + matrix[A][B] + "-" + datas[B] +
'>';
}
}
public Graph(int N) {
this.N = N;
matrix = new int[N][N];
statuses = new Status[N];
datas = (T[]) new Object[N]; // 泛型數(shù)組實(shí)例化
}
/**
* 鄰接矩陣保存的信息是從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)的信息
*
* @param from 從這個(gè)節(jié)點(diǎn)
* @param to 指向這個(gè)節(jié)點(diǎn)
* @param weight 路徑權(quán)重
* @return void
*/
public void setMatrix(int from, int to, int weight) {
matrix[from][to] = weight;
}
/**
* 設(shè)置圖的邊(matrix初始化之后才調(diào)用)
*
* @return void
*/
public void setEdges() {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] > 0) {
edges.add(new Edge(i, j));
}
}
}
}
/**
* 最小生成樹(shù)中判斷是否有回路的重要方法
* 獲取索引為i的頂點(diǎn)的終點(diǎn), 用于判斷兩個(gè)頂點(diǎn)的終點(diǎn)是否相同
*
* @param ends 記錄各個(gè)頂點(diǎn)的終點(diǎn)(遍歷過(guò)程中才動(dòng)態(tài)確定的數(shù)組)
* @param i 傳入的頂點(diǎn)索引
* @return int 原頂點(diǎn)的終點(diǎn)索引
*/
private int getEnd(int[] ends, int i) {
System.out.print(datas[i] + "->");
while (ends[i] != 0) { // 艸我懂了: 循環(huán)是為了找到最終的終點(diǎn)
i = ends[i];
}
System.out.println(datas[i]);
return i;
}
/**
* 克魯斯卡爾算法-最小生成樹(shù)
*
* @return void
*/
public void KruskalTree() {
// ends保存取出各個(gè)邊后依次拼接時(shí), 各個(gè)頂點(diǎn)的終點(diǎn)索引
int[] ends = new int[N];
// 把邊的權(quán)重排序
edges.sort(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return matrix[o1.A][o1.B] - matrix[o2.A][o2.B];
}
});
// 保存最小生成樹(shù)中包含的邊集合
List<Edge> result = new ArrayList<>();
// 依次取出并拼接
for (Edge edge : edges) {
// 如果這條邊取出來(lái)拼接后構(gòu)成環(huán), 則取消拼接操作
int endOfA = getEnd(ends, edge.A);
int endOfB = getEnd(ends, edge.B);
// 如果邊的第一個(gè)頂點(diǎn)的終點(diǎn)不等于第二個(gè)頂點(diǎn)的終點(diǎn)
if (endOfA != endOfB) {
// 設(shè)置第一個(gè)頂點(diǎn)的終點(diǎn)的終點(diǎn)為第二個(gè)頂點(diǎn)的終點(diǎn)
ends[endOfA] = endOfB;
result.add(edge);
}
}
System.out.println(result);
// 返回最小生成樹(shù)的鄰接矩陣
int[][] treeMatrix = new int[N][N];
for (Edge edge : result) {
treeMatrix[edge.A][edge.B] = matrix[edge.A][edge.B];
}
System.out.println("最小生成樹(shù)的鄰接矩陣: ");
for (int[] nums : treeMatrix) {
System.out.println(Arrays.toString(nums));
}
}
public static void main(String[] args) {
Graph<String> graph = new Graph<>(6);
graph.setDatas(new String[]{"A", "B", "C", "D", "E", "F"});
// {端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值}
int[][] set = {{0, 1, 1},
{0, 2, 3},
{1, 3, 2},
{1, 5, 2},
{2, 3, 4},
{2, 5, 7},
{3, 4, 1},
{4, 5, 8}};
for (int i = 0; i < set.length; i++) {
// graph.setMatrix(端點(diǎn)索引, 端點(diǎn)索引, 權(quán)值)
graph.setMatrix(set[i][0], set[i][1], set[i][2]);
}
graph.setEdges();
graph.KruskalTree();
}
}
謝謝沈矿，第一次寫(xiě)文，不喜輕噴咬腋，狗頭保命
