java如何實現最小高度樹

這篇文章主要為大家展示了java如何實現最小高度樹，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶大家一起來研究并學習一下“java如何實現最小高度樹”這篇文章吧。

對于一個具有樹特征的無向圖，我們可選擇任何一個節(jié)點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹并返回他們的根節(jié)點。

格式

該圖包含 n 個節(jié)點，標記為 0 到 n - 1。給定數字 n 和一個無向邊 edges 列表（每一個邊都是一對標簽）。

你可以假設沒有重復的邊會出現在 edges 中。由于所有的邊都是無向邊， [0, 1]和 [1, 0] 是相同的，因此不會同時出現在 edges 里。

示例 1:

輸入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]         0         |         1        / \       2   3  輸出: [1]

示例 2:

輸入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]      0  1  2       \ | /         3         |         4         |         5  輸出: [3, 4]

說明:

1，根據樹的定義，樹是一個無向圖，其中任何兩個頂點只通過一條路徑連接。換句話說，一個任何沒有簡單環(huán)路的連通圖都是一棵樹。

2，樹的高度是指根節(jié)點和葉子節(jié)點之間最長向下路徑上邊的數量。

答案：

 1public List<Integer> findMinHeightTrees(int n, int[][] edges) {
 2    if (n == 1)
 3        return Collections.singletonList(0);
 4    List<Set<Integer>> adj = new ArrayList<>(n);
 5    for (int i = 0; i < n; ++i)
 6        adj.add(new HashSet<>());
 7    for (int[] edge : edges) {
 8        adj.get(edge[0]).add(edge[1]);
 9        adj.get(edge[1]).add(edge[0]);
10    }
11    List<Integer> leaves = new ArrayList<>();
12    for (int i = 0; i < n; ++i)
13        if (adj.get(i).size() == 1)
14            leaves.add(i);
15    while (n > 2) {
16        n -= leaves.size();
17        List<Integer> newLeaves = new ArrayList<>();
18        for (int i : leaves) {
19            int j = adj.get(i).iterator().next();
20            adj.get(j).remove(i);
21            if (adj.get(j).size() == 1)
22                newLeaves.add(j);
23        }
24        leaves = newLeaves;
25    }
26    return leaves;
27}

解析：

這種解法比較簡單，這里注意第19行，adj.get(i)獲取的HashSet的size是等于1的。第20行會把葉子節(jié)點i給移除掉。我們先看個圖更有助于理解

比如這個，他是不停的把葉子節(jié)點去掉，直到最后剩下一個或2個節(jié)點的時候停止循環(huán)。

Java的優(yōu)點是什么

1. 簡單，只需理解基本的概念，就可以編寫適合于各種情況的應用程序；2. 面向對象；3. 分布性，Java是面向網絡的語言；4. 魯棒性，java提供自動垃圾收集來進行內存管理，防止程序員在管理內存時容易產生的錯誤。；5. 安全性，用于網絡、分布環(huán)境下的Java必須防止病毒的入侵。6. 體系結構中立，只要安裝了Java運行時系統(tǒng)，就可在任意處理器上運行。7. 可移植性，Java可以方便地移植到網絡上的不同機器。8.解釋執(zhí)行，Java解釋器直接對Java字節(jié)碼進行解釋執(zhí)行。

以上就是關于“java如何實現最小高度樹”的內容，如果該文章對您有所幫助并覺得寫得不錯，勞請分享給您的好友一起學習新知識，若想了解更多相關知識內容，請多多關注億速云行業(yè)資訊頻道。