package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
int[][] adjustMatrix = {
{0,7,-1,5,-1,-1,-1},
{-1,0,8,9,7,-1,-1},
{-1,-1,0,-1,5,-1,-1},
{-1,-1,-1,0,15,6,-1},
{-1,-1,-1,-1,0,8,9},
{-1,-1,-1,-1,-1,0,11},
{-1,-1,-1,-1,-1,-1,0}
};
MergeSearchSet.gainSpanningTree(adjustMatrix);
}
}
package com.company;
/**
* 并查集是干嗎用的治筒？也就是說它有啥實用價值仅财？
* 實用價值是用于判斷無向連通圖里面有沒有環(huán)。
* 什么是環(huán)呢楼镐？很形象的名詞，意思就跟這個字本
* 身一樣啥么，是個回路登舞、圓圈、死胡同悬荣、死心眼菠秒、洞
* 等。從幾何的角度講就是在無向連通圖中的氯迂，由
* 頂點和邊組成的践叠，封閉的，不開口的幾何圖形嚼蚀。
* 再具體點的例子就是禁灼，A到B連通，B到C連通轿曙，C
* 到A連通弄捕，那么ABC和它們之間的邊就形成了環(huán)，
* 假如C到A不連通那它們之間就不構(gòu)成環(huán)导帝。
*/
public class MergeSearchSet {
/**
* 并查集最典型的應(yīng)用就是用于生成樹
* 守谓，不過和最小生成樹不同，這里只需
* 要能獲取到生成樹即可您单。
* @param sourceArray
*/
static public void gainSpanningTree(int[][] sourceArray) {
int arrayLength = sourceArray.length;
//不像克魯斯卡爾算法那樣分飞，這
// 里在獲取邊權(quán)的時候不需要排序。
SingleLinkNode headPointer = new SingleLinkNode(-1,-1,-1);
for (int counter = 0;counter < arrayLength;counter++) {
for (int counter0 = counter + 1;counter0 < arrayLength;counter0++) {
if (sourceArray[counter][counter0] > 0) {
SingleLinkNode newNode = new SingleLinkNode(counter,counter0,sourceArray[counter][counter0]);
newNode.nextPointer = headPointer.nextPointer;
headPointer.nextPointer = newNode;
}
}
}
//創(chuàng)建一個數(shù)組用來記錄每個頂點的
// 根結(jié)點睹限，因為本算的思想就是最
// 小的連通子圖是一棵樹譬猫，既然是
// 樹那必然有根結(jié)點，如果倆結(jié)點
// 的根結(jié)點相同那就代表它倆在同
// 一棵樹上羡疗。然后我用一個數(shù)組來
// 記錄每個結(jié)點的根結(jié)點染服，一開始
// 的時候每個結(jié)點所屬的集合的根
// 結(jié)點就是該結(jié)點自身。
int[] rootArray = new int[arrayLength];
for (int counter = 0;counter < arrayLength;counter++)
rootArray[counter] = counter;
System.out.println("一開始的前驅(qū)根結(jié)點");
for (int element:rootArray)
System.out.print(element + " ");
System.out.println();
//現(xiàn)在遍歷這個鏈表
SingleLinkNode currentPointer = headPointer;
while (currentPointer.nextPointer != null) {
SingleLinkNode targetPointer = currentPointer.nextPointer;
int rootNodeSource = findRootIndex(targetPointer.getSourceNode(),rootArray);
int rootNodeTarget = findRootIndex(targetPointer.getTargetNode(),rootArray);
if (rootNodeSource == rootNodeTarget) {
//這說明這倆結(jié)點在同一個樹中于是舍去
System.out.println("\n屬于同一集合的(" + targetPointer.getSourceNode()
+ "," + targetPointer.getTargetNode() + ")舍去");
System.out.println("并把頂點對(" + targetPointer.getSourceNode()
+ "," + targetPointer.getTargetNode() + ")從鏈表中摳去");
currentPointer.nextPointer = targetPointer.nextPointer;
targetPointer = null;
} else {
System.out.println("\n現(xiàn)在處理屬于不同集合的(" + targetPointer.getSourceNode()
+ "," + targetPointer.getTargetNode() + ")");
System.out.println("把頂點" + targetPointer.getTargetNode() + "所屬樹作為子樹連接到" +
targetPointer.getSourceNode() + "所屬的樹上叨恨。");
//關(guān)鍵在于你要把找到的共同的根結(jié)點連在一起柳刮。
// 因為你是要把一棵樹A作為子樹連接到另一棵樹B
// 的樹根結(jié)點處的，從而讓A和原來這棵樹B形成兄
// 弟關(guān)系痒钝。
rootArray[rootNodeSource] = rootArray[rootNodeTarget];
System.out.println("刷新后的前驅(qū)根結(jié)點");
for (int element:rootArray)
System.out.print(element + " ");
System.out.println();
currentPointer = currentPointer.nextPointer;
}
}
//最后查看生成樹中的有哪些頂點和邊
System.out.println("\n生成樹中的頂點和邊權(quán)");
while (headPointer.nextPointer != null) {
System.out.println("(" + headPointer.nextPointer.getSourceNode() +
"," + headPointer.nextPointer.getTargetNode() +
")-->" + headPointer.nextPointer.getWeight());
headPointer = headPointer.nextPointer;
}
}
/**
* 該方法有2個作用秉颗。
* 1送矩、首先把找到該結(jié)點所屬根結(jié)點。
* 2栋荸、把尋找過程中所有的中間結(jié)點的
* 根結(jié)點統(tǒng)統(tǒng)置為找到的那個根結(jié)點菇怀。
* 它每次只能處理一條樹枝，把父子關(guān)
* 系變成兄弟關(guān)系爱沟。
* @param index
* @param rootArray
* @return
*/
static private int findRootIndex(int index,int[] rootArray) {
//首先找根節(jié)點所在。
int currentIndex = index;
while (rootArray[currentIndex] != currentIndex)
currentIndex = rootArray[currentIndex];
int targetRootIndex = currentIndex;
//更新沿途所有中間結(jié)點的根結(jié)點為targetRootIndex呼伸。
currentIndex = index;
while (rootArray[currentIndex] != targetRootIndex) {
currentIndex = rootArray[currentIndex];
rootArray[currentIndex] = targetRootIndex;
}
return targetRootIndex;
}
}
package com.company;
public class SingleLinkNode {
private int sourceNode;
private int targetNode;
private int weight;
public SingleLinkNode nextPointer = null;
public SingleLinkNode(int sourceNode, int targetNode, int weight) {
this.sourceNode = sourceNode;
this.targetNode = targetNode;
this.weight = weight;
}
public int getWeight() {
return weight;
}
public int getSourceNode() {
return sourceNode;
}
public int getTargetNode() {
return targetNode;
}
}
打印輸出
一開始的前驅(qū)根結(jié)點
0 1 2 3 4 5 6
現(xiàn)在處理屬于不同集合的(5,6)
把頂點6所屬樹作為子樹連接到5所屬的樹上。
刷新后的前驅(qū)根結(jié)點
0 1 2 3 4 6 6
現(xiàn)在處理屬于不同集合的(4,6)
把頂點6所屬樹作為子樹連接到4所屬的樹上括享。
刷新后的前驅(qū)根結(jié)點
0 1 2 3 6 6 6
屬于同一集合的(4,5)舍去
并把頂點對(4,5)從鏈表中摳去
現(xiàn)在處理屬于不同集合的(3,5)
把頂點5所屬樹作為子樹連接到3所屬的樹上。
刷新后的前驅(qū)根結(jié)點
0 1 2 6 6 6 6
屬于同一集合的(3,4)舍去
并把頂點對(3,4)從鏈表中摳去
現(xiàn)在處理屬于不同集合的(2,4)
把頂點4所屬樹作為子樹連接到2所屬的樹上奶浦。
刷新后的前驅(qū)根結(jié)點
0 1 6 6 6 6 6
現(xiàn)在處理屬于不同集合的(1,4)
把頂點4所屬樹作為子樹連接到1所屬的樹上踢星。
刷新后的前驅(qū)根結(jié)點
0 6 6 6 6 6 6
屬于同一集合的(1,3)舍去
并把頂點對(1,3)從鏈表中摳去
屬于同一集合的(1,2)舍去
并把頂點對(1,2)從鏈表中摳去
現(xiàn)在處理屬于不同集合的(0,3)
把頂點3所屬樹作為子樹連接到0所屬的樹上澳叉。
刷新后的前驅(qū)根結(jié)點
6 6 6 6 6 6 6
屬于同一集合的(0,1)舍去
并把頂點對(0,1)從鏈表中摳去
生成樹中的頂點和邊權(quán)
(5,6)-->11
(4,6)-->9
(3,5)-->6
(2,4)-->5
(1,4)-->7
(0,3)-->5
