每日“力扣”系列 50 圖的複製
今天開始做幾道關於“圖”的演算法題，今天的是力扣第133題，難度“中等”。題目描述如下：
這裡可能有些朋友還不知道什麼是“圖”，簡單介紹一下，圖是一種可以儲存相互關係的資料結構，具體又可以分為有向圖和無向圖（今天的題目用到的就是無向圖），至於什麼是向：
想想兩個物件，A ，B ，如果A與B是相互連線在一起的，就說這個連線是一條邊，二者也就是有關係的，當更多的物件C，D，E也加入進來後，其關係就會變得更加的複雜，圖就是可以儲存這樣一種關係的資料結構，當然，對於這個連線關係，怎麼解釋就是看你的想法了，可以解釋為兩個路口連線，或者說是二人有好友關係等等。
如果在相互關係的基礎上，我們還添加了方向的概念，那就變成了有向圖，舉例來說說，A，B分別代表著兩個人，從A指向B，則說明A是B的一個粉絲，如果同時B也是A的粉絲，則在儲存時也會有一條從B指向A的邊。這就是有向圖了。當然粉絲問題只是其中一個用法。
圖中有相互關係，或者說是二者之間有“邊”的兩個物件，就互為對方的鄰居。相互連線就是鄰居，也很好理解是吧。
今天這個複製的題目涉及到的就是一種無向圖，現在使用的是一個連結串列來儲存某個物件的鄰居節點，這個題目要做的就是要將所有的節點以及其鄰居分別複製。要實現這個目的，我們有兩種方法，分別是“深度優先演算法”與“廣度優先演算法”，下面我將盡力將這兩個方法給你解釋清楚。
首先我們需要知道，為了避免對一個節點重複訪問複製，我們需要對複製過的節點進行標記，當之後再次訪問這個物件時，如果看到了這個標誌，就說明這個物件是已經複製過了，反之，則進行復制，然後將這個物件進行標記。
這裡考慮查詢的快速性，我們使用HashMap來儲存已經複製過的節點。一個鍵值對儲存的就是原物件與其複製的物件（這裡是看懂下面具體程式碼時需要注意的）。
我們先來看深度優先演算法。
深度優先演算法，通俗來講，就是“一條路走到黑”。
當訪問一個物件時，我們先找他的一個鄰居，而後找鄰居的一個鄰居（當然不能是之前訪問過的，否則會造成死迴圈。），一直找下去，直到這個鄰居沒有能夠鄰居再也麼有鄰居沒有被訪問了。
圖片來自於某網路課程
就像上圖展示的，從S開始，先找鄰居，此時2，4都沒有被訪問過，假設找了2，之後2再繼續找鄰居，找到了5，5的鄰居有4，此時與 4 有邊的元素都已經被考察過了，那就直接返回。
private
HashMap
<
Node
，
Node
>
visited
=
new
HashMap
<>（）；
public
Node
cloneGraph
（
Node
n
）{
if
（
n
==
null
）{
return
n
；
}
if
（
visited
。
containsKey
（
n
））{
return
visited
。
get
（
n
）；
}
Node
cloneNode
=
new
Node
（
n
。
val
，
new
ArrayList
<>（））；
visited
。
put
（
n
，
cloneNode
）；
for
（
Node
neighbor
：
n
。
neighbors
）{
cloneNode
。
neighbors
。
add
（
cloneGraph
（
neighbor
））；
}
return
cloneNode
；
}
這裡藉助了遞迴的設計思路。
其次是廣度搜索的演算法，如果說深度優先是“一條路走到黑”，那麼廣度優先演算法就可以說是“廣播”，同等距離的物件在一個位置進行考察、也就是說對於某一個物件的鄰居，在同一處進行復制操作。
盜圖無理，請見諒
對應的程式碼就是這樣的：
public
Node
cloneGraph2
（
Node
n
）{
if
（
n
==
null
）{
return
n
；
}
HashMap
<
Node
，
Node
>
visited
=
new
HashMap
<>（）；
LinkedList
<
Node
>
queue
=
new
LinkedList
<
Node
>（）；
queue
。
add
（
n
）；
visited
。
put
（
n
，
new
Node
（
n
。
val
，
new
ArrayList
（）））；
while
（！
queue
。
isEmpty
（））{
Node
node
=
queue
。
remove
（）；
for
（
Node
neighbor
：
node
。
neighbors
）{
if
（！
visited
。
containsKey
（
neighbor
））{
visited
。
put
（
neighbor
，
new
Node
（
neighbor
。
val
，
new
ArrayList
<>（）））；
queue
。
add
（
neighbor
）；
}
visited
。
get
（
node
）。
neighbors
。
add
（
visited
。
get
（
neighbor
））；
}
}
return
visited
。
get
（
n
）；
}
從佇列首部取出一個節點。
遍歷該節點的所有鄰居節點。
如果某個鄰接點已被訪問，那麼這個節點一定在 visited 中，直接返回。
否則，建立一個新的節點儲存在 visited 中。
將複製的鄰接點新增到複製圖對應節點的鄰居列表中。
這幾個周復課後，化學+計算機的課程壓力有點大，天天總結演算法題可能有點吃力，暫時停更一段時間，稍微閒散一點了繼續寫。當然，刷題是不可能停止的！
王進林：每日“力扣”系列 49 陣列交集王進林：每日“力扣”系列 48 H指數
今日配圖“阿卡迪亞國家公園”圖片來源於網路，侵刪。
