??今天做了一道很有意思的一道題沙峻，這道題雖然難度只是中等滨彻，但是里面涉及到的東西卻是不少。其中，我在里面學(xué)習(xí)到了并查集這個(gè)東西逗余，雖然不是很深刻霍殴，至少有一個(gè)印象坟岔；還有深搜顶瞳，一直以來(lái)，深搜和廣搜都是我的弱項(xiàng)赶促，本文的理解是基于別人的博客： lintcode178. graph valid tree 圖是否是樹液肌。我們來(lái)看看題
題意
給出 n 個(gè)節(jié)點(diǎn)，標(biāo)號(hào)分別從 0 到 n - 1 并且給出一個(gè) 無(wú)向 邊的列表 (給出每
條邊的兩個(gè)頂點(diǎn)), 寫一個(gè)函數(shù)去判斷這張｀無(wú)向｀圖是否是一棵樹
樣例
給出n = 5 并且 edges = [[0, 1], [0, 2], [0, 3], [1, 4]], 返回 true.
給出n = 5 并且 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], 返回 false.
注意事項(xiàng)
你可以假設(shè)我們不會(huì)給出重復(fù)的邊在邊的列表當(dāng)中. 無(wú)向邊 [0, 1] 和 [1, 0]
是同一條邊鸥滨， 因此他們不會(huì)同時(shí)出現(xiàn)在我們給你的邊的列表當(dāng)中嗦哆。
1.并查集
??首先有兩點(diǎn)：
?? A.如果點(diǎn)的個(gè)數(shù)減去邊數(shù)不等于1，此圖肯定不為樹婿滓。
??B.如果有一條邊的兩個(gè)點(diǎn)同屬于一個(gè)集合的話老速，那么此圖肯定不為樹
??第一點(diǎn)我們非常容易的能夠判斷出來(lái)，但是第二種怎么來(lái)判斷呢凸主？這就需要我們的并查集(我也是第一次接觸到并查集橘券，只是知道它的模型，所以可能說(shuō)的不是很清楚)。
(1).一維數(shù)組記錄每一個(gè)點(diǎn)的集合
??我們首先可以定義一個(gè)一維數(shù)組旁舰，默認(rèn)全部初始化為-1锋华，其中表示的意思就是：假設(shè)數(shù)組temp[], temp[0]表示的是0這個(gè)點(diǎn)屬于的集合，不同的集合我們不同數(shù)字來(lái)表示箭窜，比如毯焕，0集合和1集合是不同的，同一個(gè)集合的點(diǎn)構(gòu)成了一棵樹磺樱。
??具體的操作：
??當(dāng)我們遍歷到一條邊時(shí)纳猫，判斷這條邊的兩個(gè)點(diǎn)是否在temp數(shù)組中出現(xiàn)，其中分為三種情況：
??A.兩個(gè)點(diǎn)均未出現(xiàn)竹捉，也就是兩個(gè)點(diǎn)對(duì)應(yīng)的temp數(shù)組的值是等于-1芜辕，那么，我們將這兩個(gè)點(diǎn)對(duì)應(yīng)的數(shù)組值更為兩點(diǎn)中最小的那個(gè)點(diǎn)(這里沒(méi)有限制活孩，最大也行物遇，主要是保證他們倆在同一個(gè)集合中)。
??B.一個(gè)點(diǎn)出現(xiàn)過(guò)憾儒，一個(gè)點(diǎn)未出現(xiàn)，那么我們將未出現(xiàn)的那個(gè)點(diǎn)對(duì)應(yīng)的數(shù)組值更新為出現(xiàn)的那個(gè)點(diǎn)的數(shù)組值乃沙，這樣就保證了兩個(gè)點(diǎn)屬于同一個(gè)集合起趾。
??C.兩個(gè)點(diǎn)都出現(xiàn)過(guò)，只是屬于不同的集合警儒，也就是說(shuō)训裆，兩個(gè)點(diǎn)對(duì)應(yīng)的數(shù)組值不相同，那么此時(shí)我們的操作是將兩個(gè)集合合并起來(lái)蜀铲，具體的操作是：因?yàn)槊總€(gè)集合里面的所有值都是相同边琉，那么我們將值較大的那個(gè)集合的值全部更新為另一個(gè)集合的值，比如有兩個(gè)集合分別是：{1,1}记劝，{2,2}变姨，更新過(guò)后就是：{1,1,1,1}。這樣能保證兩個(gè)集合合并起來(lái)后厌丑，構(gòu)成一個(gè)集合定欧。
??D.兩個(gè)點(diǎn)都出現(xiàn)過(guò)，同時(shí)還屬于同一個(gè)集合怒竿，那么此圖肯定不為樹砍鸠。
代碼
public boolean validTree(int n, int[][] edges) {
//當(dāng)點(diǎn)數(shù)減去邊數(shù)不等于1時(shí)，肯定不為樹
if (n - edges.length != 1) {
return false;
}
int temp[] = new int[n];
for (int i = 0; i < edges.length; i++) {
int node1 = edges[i][0];
int node2 = edges[i][1];
// 當(dāng)兩個(gè)點(diǎn)屬于同一個(gè)集合時(shí)耕驰，要么兩點(diǎn)沒(méi)有在任何集合里面爷辱，要么在同一個(gè)集合里面
if (temp[node1] == temp[node2]) {
//都沒(méi)有出現(xiàn)過(guò)
if (temp[node1] == -1) {
temp[node1] = temp[node2] = Math.min(node1, node2);
} else { //都出現(xiàn)過(guò)，同時(shí)還屬于同一個(gè)集合
return false;
}
} else {
// 當(dāng)兩個(gè)點(diǎn)都在集合里面，但是是在不同的集合里饭弓，更新集合
if (temp[node1] != -1 && temp[node2] != -1) {
int max = Math.max(temp[node1], temp[node2]);
int min = Math.min(temp[node1], temp[node2]);
for (int j = 0; j < n; j++) {
if (temp[j] == max) { //將值較大的集合的值全部更新min
temp[j] = min;
}
}
} else { // 當(dāng)只有一個(gè)點(diǎn)在集合里面
if (temp[node1] != -1) {
temp[node2] = temp[node1];
} else {
temp[node1] = temp[node2];
}
}
}
}
return true;
}
如圖所示
2.深搜遍歷
??深搜遍歷在這里主要作用是：我們尋找每一個(gè)點(diǎn)的父節(jié)點(diǎn)双饥，如果兩個(gè)點(diǎn)的父節(jié)點(diǎn)相同的話，那么此圖肯定不為樹示启。這里的理解上可能有一些問(wèn)題兢哭，我們看看下面的幾種情況：
(1).兩個(gè)點(diǎn)均是第一次出現(xiàn)。如圖：
(2).一個(gè)點(diǎn)是出現(xiàn)過(guò)的夫嗓，另一個(gè)點(diǎn)是第一次出現(xiàn)迟螺。如圖(提示一下，下面圖的描述錯(cuò)了舍咖，C的父親應(yīng)該是A)：
(3).兩個(gè)點(diǎn)都有父親矩父，只是父親不相同，分為兩種情況：
(4).兩個(gè)點(diǎn)都出現(xiàn)過(guò)排霉，并且父親相同窍株，分為兩種情況:
代碼
private int dfs(int temp[], int node){
//當(dāng)這個(gè)點(diǎn)不在有父親了，返回這個(gè)點(diǎn)
if(temp[node] == -1){
return node;
}
else //如果這點(diǎn)還有父親的話攻柠，那么就繼續(xù)遍歷這個(gè)點(diǎn)的父親
{
return dfs(temp, temp[node]);
}
}
public boolean validTree(int n, int[][] edges) {
if (n - edges.length != 1) {
return false;
}
int []temp = new int[n];
Arrays.fill(temp,-1);
for(int i = 0; i < edges.length; i++){
//獲取edges[i][0]點(diǎn)的父親
int node1 = dfs(temp, edges[i][0]);
//獲取edges[i][1]點(diǎn)的父親
int node2 = dfs(temp, edges[i][0]);
//如果父親相同的話球订，肯定不為樹
if(node1 == node2){
return false;
}
//將node2的父親設(shè)置為node1
temp[node2] = node1;
}
return true;
}
