資訊專欄INFORMATION COLUMN
摘要：現(xiàn)在要求在這樣一棵生成樹(shù)中，找到生成樹(shù)的高度最低的所有根節(jié)點(diǎn)。然后利用鄰接表的相關(guān)屬性來(lái)判斷當(dāng)前節(jié)點(diǎn)是否是葉節(jié)點(diǎn)。度數(shù)為一的頂點(diǎn)就是葉節(jié)點(diǎn)。這里使用異或的原因是對(duì)同一個(gè)值進(jìn)行兩次異或即可以回到最初值。
題目
For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1 :
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/
2 3
Output: [1]
Example 2 :
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
| /
3
|
4
|
5
Output: [3, 4]
Note:
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
在無(wú)向圖的生成樹(shù)中，我們可以指定任何一個(gè)節(jié)點(diǎn)為這棵樹(shù)的根節(jié)點(diǎn)。現(xiàn)在要求在這樣一棵生成樹(shù)中，找到生成樹(shù)的高度最低的所有根節(jié)點(diǎn)。
其實(shí)，決定一棵樹(shù)的高度往往是樹(shù)中的最長(zhǎng)路徑，只有我們選擇最長(zhǎng)路徑的中間點(diǎn)才能夠盡可能減少樹(shù)的高度。那么我們?nèi)绾握业剿械闹虚g節(jié)點(diǎn)呢？
當(dāng)出發(fā)點(diǎn)只有兩個(gè)時(shí)，我們知道中間節(jié)點(diǎn)就是從出發(fā)點(diǎn)同時(shí)出發(fā)，當(dāng)二者相遇或者二者只間隔一個(gè)位置是所在的點(diǎn)就是兩個(gè)出發(fā)點(diǎn)的重點(diǎn)。那么多個(gè)出發(fā)點(diǎn)也是同樣的道理，每個(gè)人從各個(gè)出發(fā)點(diǎn)出發(fā)，最終相遇的點(diǎn)就是我們所要找的中間點(diǎn)。
這題的思路有些類似于拓?fù)渑判?，每次我們都?huì)去除所有入度為0的點(diǎn)，因?yàn)檫@些點(diǎn)肯定是葉節(jié)點(diǎn)。然后不停的往中間走，直到剩下最后一個(gè)葉節(jié)點(diǎn)或是最后兩個(gè)葉節(jié)點(diǎn)。
0 | 1 / 2 3
這個(gè)圖中刪除所有入度為0的點(diǎn)就只剩下1，因此我們知道1一定就是我們所要求的根節(jié)點(diǎn)
思路一：圖論這一種解法著重強(qiáng)調(diào)了利用圖論中的數(shù)據(jù)結(jié)構(gòu)來(lái)解決問(wèn)題。這里我們采用圖論中的鄰接表來(lái)存儲(chǔ)圖中的點(diǎn)和邊。然后利用鄰接表的相關(guān)屬性來(lái)判斷當(dāng)前節(jié)點(diǎn)是否是葉節(jié)點(diǎn)。
