image.png
0. 鏈接
1. 題目
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}
Test case format:
For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.
Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
示意圖
Example 1:
示意圖
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:
示意圖
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Example 4:
示意圖
Input: adjList = [[2],[1]]
Output: [[2],[1]]
Constraints:
1 <= Node.val <= 100
Node.val is unique for each node.
Number of Nodes will not exceed 100.
There is no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
2. 思路1: 隊(duì)列+BFS
- 基本思路是:
- 初始化一個(gè)隊(duì)列蜗帜，將任意一個(gè)節(jié)點(diǎn)作為起始節(jié)點(diǎn)，添加到隊(duì)尾博脑；初始化一個(gè)字典dic<原始節(jié)點(diǎn), 拷貝節(jié)點(diǎn)>
- 每次從隊(duì)頭pop出一個(gè)節(jié)點(diǎn), 然后把它的鄰居節(jié)點(diǎn)逐個(gè)添加到隊(duì)尾 這樣就確保了FIFO的特性, 達(dá)成了寬度搜索
- 處理每個(gè)節(jié)點(diǎn)的時(shí)候, 遍歷它的每個(gè)鄰居堪遂， 判斷它是否處理過(guò)(即在dic中有它), 如果沒(méi)有, 則實(shí)施節(jié)點(diǎn)拷貝, 并添加到dic中卷拘； 且記錄拷貝鄰居節(jié)點(diǎn)成為當(dāng)前拷貝節(jié)點(diǎn)的鄰居
- 直至隊(duì)列為空, 則由于圖的連通性, 所有節(jié)點(diǎn)都已處理完畢
- 分析:
- 所有節(jié)點(diǎn)
N都被遍歷常數(shù)次, 且所有邊E都被遍歷常數(shù)次, 查找是否遍歷過(guò)依賴(lài)dic的O(1)查找特性, 于是時(shí)間復(fù)雜度為O(N+E), 空間復(fù)雜度O(N)
- 復(fù)雜度
- 時(shí)間復(fù)雜度
O(N+E) - 空間復(fù)雜度
O(N)
3. 代碼
# coding:utf8
import collections
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
# BFS
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node is None:
return None
dic = dict()
queue = collections.deque()
node_copy = Node(node.val)
queue.append(node)
dic[node] = node_copy
while len(queue) > 0:
head = queue.popleft()
for neighbor in head.neighbors:
if neighbor not in dic:
# 遇到新節(jié)點(diǎn), 則拷貝新節(jié)點(diǎn)內(nèi)容到目標(biāo)容器
neighbor_copy = Node(neighbor.val)
queue.append(neighbor)
dic[neighbor] = neighbor_copy
# 補(bǔ)齊head和neighbor之間的連接關(guān)系
dic[head].neighbors.append(neighbor_copy)
else:
# 補(bǔ)齊head和neighbor之間的連接關(guān)系
dic[head].neighbors.append(dic[neighbor])
return node_copy
def print_graph(node1):
queue = collections.deque()
queue.append(node1)
visited_set = set()
while len(queue) > 0:
head = queue.popleft()
if head in visited_set:
continue
visited_set.add(head)
neighbors = list()
for neighbor in head.neighbors:
neighbors.append(neighbor.val)
if neighbor not in visited_set:
queue.append(neighbor)
print('node.val={}, neigbors: {}'.format(head.val, neighbors))
solution = Solution()
graph1 = node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node1.neighbors += [node2, node4]
node2.neighbors += [node1, node3]
node3.neighbors += [node2, node4]
node4.neighbors += [node1, node3]
print('input:')
print_graph(graph1)
print('*' * 10)
graph1_copy = solution.cloneGraph(graph1)
print('output:')
print_graph(graph1_copy)
print('=' * 50)
輸出結(jié)果
input:
node.val=1, neigbors: [2, 4]
node.val=2, neigbors: [1, 3]
node.val=4, neigbors: [1, 3]
node.val=3, neigbors: [2, 4]
**********
output:
node.val=1, neigbors: [2, 4]
node.val=2, neigbors: [1, 3]
node.val=4, neigbors: [1, 3]
node.val=3, neigbors: [2, 4]
==================================================
4. 結(jié)果
image.png
5. 思路2: 棧+DFS
- 過(guò)程
- 與BFS相比氢橙， 唯一的區(qū)別是, 循環(huán)里每次都取出棧尾元素進(jìn)行處理, 這樣，它遍歷節(jié)點(diǎn)的順序就變成了緊跟節(jié)點(diǎn)入棧的節(jié)奏, 先找到一條到達(dá)終點(diǎn)的最深路徑, 再處理其他路徑, 即為深度優(yōu)先搜索
- 分析
同BFS相同 - 時(shí)間復(fù)雜度
O(N+E) - 空間復(fù)雜度
O(N)
6. 代碼
# coding:utf8
import collections
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
# DFS
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node is None:
return None
dic = dict()
stack = list()
node_copy = Node(node.val)
dic[node] = node_copy
stack.append(node)
while len(stack) > 0:
last = stack.pop()
for neighbor in last.neighbors:
if neighbor not in dic:
neighbor_copy = Node(neighbor.val)
stack.append(neighbor)
dic[neighbor] = neighbor_copy
dic[last].neighbors.append(dic[neighbor])
else:
dic[last].neighbors.append(dic[neighbor])
return node_copy
def print_graph(node1):
queue = collections.deque()
queue.append(node1)
visited_set = set()
while len(queue) > 0:
head = queue.popleft()
if head in visited_set:
continue
visited_set.add(head)
neighbors = list()
for neighbor in head.neighbors:
neighbors.append(neighbor.val)
if neighbor not in visited_set:
queue.append(neighbor)
print('node.val={}, neigbors: {}'.format(head.val, neighbors))
solution = Solution()
graph1 = node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node1.neighbors += [node2, node4]
node2.neighbors += [node1, node3]
node3.neighbors += [node2, node4]
node4.neighbors += [node1, node3]
print('input:')
print_graph(graph1)
print('*' * 10)
graph1_copy = solution.cloneGraph(graph1)
print('output:')
print_graph(graph1_copy)
print('=' * 50)
輸出結(jié)果
input:
node.val=1, neigbors: [2, 4]
node.val=2, neigbors: [1, 3]
node.val=4, neigbors: [1, 3]
node.val=3, neigbors: [2, 4]
**********
output:
node.val=1, neigbors: [2, 4]
node.val=2, neigbors: [1, 3]
node.val=4, neigbors: [1, 3]
node.val=3, neigbors: [2, 4]
==================================================
7. 結(jié)果
image.png
