并查集
2018-02-22 本文已影响23人
Stroman
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;
/**
* 并查集是干吗用的？也就是说它有啥实用价值？
* 实用价值是用于判断无向连通图里面有没有环。
* 什么是环呢？很形象的名词，意思就跟这个字本
* 身一样，是个回路、圆圈、死胡同、死心眼、洞
* 等。从几何的角度讲就是在无向连通图中的，由
* 顶点和边组成的，封闭的，不开口的几何图形。
* 再具体点的例子就是，A到B连通，B到C连通，C
* 到A连通，那么ABC和它们之间的边就形成了环，
* 假如C到A不连通那它们之间就不构成环。
*/
public class MergeSearchSet {
/**
* 并查集最典型的应用就是用于生成树
* ，不过和最小生成树不同，这里只需
* 要能获取到生成树即可。
* @param sourceArray
*/
static public void gainSpanningTree(int[][] sourceArray) {
int arrayLength = sourceArray.length;
//不像克鲁斯卡尔算法那样，这
// 里在获取边权的时候不需要排序。
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;
}
}
}
//创建一个数组用来记录每个顶点的
// 根结点，因为本算的思想就是最
// 小的连通子图是一棵树，既然是
// 树那必然有根结点，如果俩结点
// 的根结点相同那就代表它俩在同
// 一棵树上。然后我用一个数组来
// 记录每个结点的根结点，一开始
// 的时候每个结点所属的集合的根
// 结点就是该结点自身。
int[] rootArray = new int[arrayLength];
for (int counter = 0;counter < arrayLength;counter++)
rootArray[counter] = counter;
System.out.println("一开始的前驱根结点");
for (int element:rootArray)
System.out.print(element + " ");
System.out.println();
//现在遍历这个链表
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) {
//这说明这俩结点在同一个树中于是舍去
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现在处理属于不同集合的(" + targetPointer.getSourceNode()
+ "," + targetPointer.getTargetNode() + ")");
System.out.println("把顶点" + targetPointer.getTargetNode() + "所属树作为子树连接到" +
targetPointer.getSourceNode() + "所属的树上。");
//关键在于你要把找到的共同的根结点连在一起。
// 因为你是要把一棵树A作为子树连接到另一棵树B
// 的树根结点处的，从而让A和原来这棵树B形成兄
// 弟关系。
rootArray[rootNodeSource] = rootArray[rootNodeTarget];
System.out.println("刷新后的前驱根结点");
for (int element:rootArray)
System.out.print(element + " ");
System.out.println();
currentPointer = currentPointer.nextPointer;
}
}
//最后查看生成树中的有哪些顶点和边
System.out.println("\n生成树中的顶点和边权");
while (headPointer.nextPointer != null) {
System.out.println("(" + headPointer.nextPointer.getSourceNode() +
"," + headPointer.nextPointer.getTargetNode() +
")-->" + headPointer.nextPointer.getWeight());
headPointer = headPointer.nextPointer;
}
}
/**
* 该方法有2个作用。
* 1、首先把找到该结点所属根结点。
* 2、把寻找过程中所有的中间结点的
* 根结点统统置为找到的那个根结点。
* 它每次只能处理一条树枝，把父子关
* 系变成兄弟关系。
* @param index
* @param rootArray
* @return
*/
static private int findRootIndex(int index,int[] rootArray) {
//首先找根节点所在。
int currentIndex = index;
while (rootArray[currentIndex] != currentIndex)
currentIndex = rootArray[currentIndex];
int targetRootIndex = currentIndex;
//更新沿途所有中间结点的根结点为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;
}
}
打印输出
一开始的前驱根结点
0 1 2 3 4 5 6
现在处理属于不同集合的(5,6)
把顶点6所属树作为子树连接到5所属的树上。
刷新后的前驱根结点
0 1 2 3 4 6 6
现在处理属于不同集合的(4,6)
把顶点6所属树作为子树连接到4所属的树上。
刷新后的前驱根结点
0 1 2 3 6 6 6
属于同一集合的(4,5)舍去
并把顶点对(4,5)从链表中抠去
现在处理属于不同集合的(3,5)
把顶点5所属树作为子树连接到3所属的树上。
刷新后的前驱根结点
0 1 2 6 6 6 6
属于同一集合的(3,4)舍去
并把顶点对(3,4)从链表中抠去
现在处理属于不同集合的(2,4)
把顶点4所属树作为子树连接到2所属的树上。
刷新后的前驱根结点
0 1 6 6 6 6 6
现在处理属于不同集合的(1,4)
把顶点4所属树作为子树连接到1所属的树上。
刷新后的前驱根结点
0 6 6 6 6 6 6
属于同一集合的(1,3)舍去
并把顶点对(1,3)从链表中抠去
属于同一集合的(1,2)舍去
并把顶点对(1,2)从链表中抠去
现在处理属于不同集合的(0,3)
把顶点3所属树作为子树连接到0所属的树上。
刷新后的前驱根结点
6 6 6 6 6 6 6
属于同一集合的(0,1)舍去
并把顶点对(0,1)从链表中抠去
生成树中的顶点和边权
(5,6)-->11
(4,6)-->9
(3,5)-->6
(2,4)-->5
(1,4)-->7
(0,3)-->5
