一、原文鏈接
http://blog.csdn.net/u014507083/article/details/71194740?locationNum=5&fps=1
二象浑、算法理解
處理一個(gè)森林之斯。當(dāng)如果希望能夠?qū)⒛晨脴?shù)并入另一棵樹(shù)下時(shí)使用瓦盛。
三喉悴、算法實(shí)現(xiàn)
1、查找根節(jié)點(diǎn)
public static int findParent(int target,int[] parent){
int parentIndex = target;
//不斷遞歸去查找根節(jié)點(diǎn)禀晓，當(dāng)panretIndex = parent[parentIndex]時(shí)即表示找到該樹(shù)的根
while (parent[parentIndex] != parentIndex)
parentIndex = parent[parentIndex];
int i = target;
//路徑壓縮柄粹，讓target節(jié)點(diǎn)及target節(jié)點(diǎn)的父節(jié)點(diǎn)指向根節(jié)點(diǎn)
while (i != parentIndex){
i = parent[i];
parent[i] = parentIndex;
}
return parentIndex;
}
2、合并樹(shù)
public static void join(int target1,int target2,int[] parent){
int root1 = findParent(target1,parent);
int root2 = findParent(target2,parent);
if (root1 != root2)
parent[root1] = root2;
}
