克隆圖

題目描述：給你無(wú)向 連通 圖中一個(gè)節(jié)點(diǎn)的引用，請(qǐng)你返回該圖的 深拷貝（克?。?。

圖中的每個(gè)節(jié)點(diǎn)都包含它的值 val（int） 和其鄰居的列表（list[Node]）。

示例說(shuō)明請(qǐng)見(jiàn)LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/clone-graph/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：深度優(yōu)先遍歷

首先，如果當(dāng)前節(jié)點(diǎn)為空，不用處理，直接返回。

否則，使用一個(gè)Map即visited來(lái)存儲(chǔ)已經(jīng)處理過(guò)的圖節(jié)點(diǎn)和相應(yīng)的克隆節(jié)點(diǎn)，遞歸處理過(guò)程如下：

• 判斷當(dāng)前節(jié)點(diǎn)是否在visited中，如果在，則說(shuō)明已經(jīng)處理過(guò)了，則直接從visited中取出當(dāng)前節(jié)點(diǎn)的克隆并返回。

• 否則，根據(jù)當(dāng)前節(jié)點(diǎn)克隆出一個(gè)新的克隆節(jié)點(diǎn)，新克隆的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)初始化為空，然后將當(dāng)前節(jié)點(diǎn)和新的克隆節(jié)點(diǎn)添加到visited中；

• 然后遞歸處理當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。

最后，返回當(dāng)前節(jié)點(diǎn)的克隆節(jié)點(diǎn)。

解法二：廣度優(yōu)先遍歷

同樣的，首先，如果當(dāng)前節(jié)點(diǎn)為空，不用處理，直接返回。

否則，也是需要初始化一個(gè)Map即visited來(lái)存儲(chǔ)已經(jīng)處理過(guò)的圖節(jié)點(diǎn)和相應(yīng)的克隆節(jié)點(diǎn)，首先將當(dāng)前節(jié)點(diǎn)和由當(dāng)前節(jié)點(diǎn)克隆的節(jié)點(diǎn)添加到visited中，然后將當(dāng)前節(jié)點(diǎn)添加到一個(gè)隊(duì)列queue中，然后處理隊(duì)列中的節(jié)點(diǎn)，知道隊(duì)列不為空，處理過(guò)程如下：

• 取出隊(duì)列的頭結(jié)點(diǎn)為curNode；

• 遍歷處理curNode節(jié)點(diǎn)的鄰居節(jié)點(diǎn)；

• 如果當(dāng)前鄰居節(jié)點(diǎn)不在visited，則將其和相應(yīng)的克隆節(jié)點(diǎn)添加到visited中，并將其加到隊(duì)列中；

• 然后將當(dāng)前鄰居節(jié)點(diǎn)的克隆節(jié)點(diǎn)添加到curNode的克隆節(jié)點(diǎn)的鄰居節(jié)點(diǎn)列表中。

最后，返回初始節(jié)點(diǎn)的克隆節(jié)點(diǎn)。

注：圖相關(guān)的算法還是了解的不多，得多學(xué)學(xué)。

【每日寄語(yǔ)】 自己動(dòng)手，豐衣足食！