133. Clone Graph

Problem

Bài toán yêu cầu bạn tạo ra một bản sao sâu (Deep copy) của một đồ thị vô hướng, liên thông, trong đó mỗi node có một giá trị và một danh sách các node neighbors. Khi clone, bạn phải đảm bảo mỗi node và mỗi cạnh đều là bản sao mới không dùng chung references với original graph

Phân tích và hướng tiếp cận

Độ thì có thể có chu trình hoặc nhiều node cùng trỏ đến một node khác, nên nếu chỉ clone “ngang” mà không nhớ các node đã clone thì sẽ bị lặp vô hạn hoặc tạo ra nhiều node clone cho cùng mọt node gốc

Do đó, cần một cấu trúc lưu lại mapping giữa node gốc và node clone (thường là Map<Node, Node>

Có hai cách duyệt: DFS hoặc BFS. Cả hai đều hợp lý, nhưng DFS thường ngắn gọn hơn trong TS

Các bước giải bằng DFS

Nếu node truyền vào là null, return null

Nếu node đã được clone (tức đã có trong map), return node clone tương ứng

Nếu node chưa được clone:

Tạo node clone mới với giá trị tương ứng

Lưu vào map (gốc → clone)

Duyệt qua từng neighbors, clone từng neighbor và thêm vào danh sách neighbors của node clone

Return node clone đầu tiên

Time and space complexity

TC: O(N + E)

SC: O(N + E)

Với:

N là số lượng node (đỉnh) trong đồ thị

E là số lượng cạnh (edge)

Solution

typescripttypescript

1/**
2 * Definition for _Node.
3 * class _Node {
4 *     val: number
5 *     neighbors: _Node[]
6 * 
7 *     constructor(val?: number, neighbors?: _Node[]) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.neighbors = (neighbors===undefined ? [] : neighbors)
10 *     }
11 * }
12 * 
13 */
14
15function cloneGraph(node: _Node | null): _Node | null {
16	const map: Map<_Node, _Node> = new Map();
17	
18	function dfs(curr: _Node | null): _Node | null {
19		if(!curr) return null;
20		if(map.has(curr)) return map.get(curr);
21		
22		const clone = new Node(curr.val);
23		map.set(curr, clone);
24		
25		for(const neighbor of curr.neighbors) {
26			clone.neighbors.push(dfs(neighbor));
27		}
28		
29		return clone;
30	}
31	
32	return dfs(node);
33};

💡

Hàm dfs vừa duyệt vừa clone, đảm bảo mỗi node chỉ clone một lần và các cạnh được giữ đúng cấu trúc gốc

map giúp tránh clone lặp và xử lý được chu trình trong đồ thị

💡

Tại sao map lại xử lý được chu trình trong đồ thị?

Khi một node được clone, nó sẽ được lưu vào Map với key là node gốc và value là node clone

Nếu gặp lại node này khi duyệt tiếp (do chu trình hoặc các đường đi giao nhau), chỉ cần trả về node clone đã lưu trong Map, không tạo mới và không tiếp tục đệ quy node này nữa

→ Nhờ vậy, mỗi node chỉ được clone đúng một lần, và chương trình không bị rơi vào vòng lặp vô hạn khi duyệt đồ thị có chu trình.

Loading content...

1/** 2 * Definition for _Node. 3 * class _Node { 4 * val: number 5 * neighbors: _Node[] 6 * 7 * constructor(val?: number, neighbors?: _Node[]) { 8 * this.val = (val===undefined ? 0 : val) 9 * this.neighbors = (neighbors===undefined ? [] : neighbors) 10 * } 11 * } 12 * 13 */ 14 15function cloneGraph(node: _Node | null): _Node | null { 16 const map: Map<_Node, _Node> = new Map(); 17 18 function dfs(curr: _Node | null): _Node | null { 19 if(!curr) return null; 20 if(map.has(curr)) return map.get(curr); 21 22 const clone = new Node(curr.val); 23 map.set(curr, clone); 24 25 for(const neighbor of curr.neighbors) { 26 clone.neighbors.push(dfs(neighbor)); 27 } 28 29 return clone; 30 } 31 32 return dfs(node); 33};

133. Clone Graph

Related Posts

Related Posts

133. Clone Graph

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists