Pattern · Tìm kiếm theo chiều sâuTrung bình
Sao Chép Đồ ThịClone Graph
Hiểu bài
Cho một nút trong đồ thị vô hướng liên thông.
- Mỗi nút chứa giá trị
val(số nguyên) và danh sách láng giềngneighbors. - Tạo ra một bản sao sâu (deep copy) của toàn bộ đồ thị.
ts
class Node {
val: number
neighbors: Node[]
constructor(val: number, neighbors: Node[] = []) {
this.val = val
this.neighbors = neighbors
}
}
// Đồ thị: 1 -- 2
// | |
// 4 -- 3
// Input: node = Node(1)
// Output: bản sao Node(1') với 1'→2'→3'→4'→1' (cấu trúc giống hệt, object khác nhau)Thách thức: đồ thị có thể có chu trình — cần Hash Map để tránh copy vô hạn.
Cách cơ bản
Không kết thúc với đồ thị có chu trìnhts
// BFS thủ công không dùng Hash Map — sẽ bị vòng lặp vô hạn với chu trình
// Đây là cách SAI để minh họa vấn đề:
function cloneGraphNaive(node: Node | null): Node | null {
if (!node) return null
const newNode = new Node(node.val)
// Nếu copy trực tiếp neighbors, sẽ copy lại node đã copy → vô hạn
for (const neighbor of node.neighbors) {
newNode.neighbors.push(cloneGraphNaive(neighbor)!) // ❌ vòng lặp vô hạn!
}
return newNode
}Vì sao cách này chậm:
Thiếu cơ chế theo dõi node đã sao chép.
Hash Map (old → new) là chìa khóa để phá chu trình.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.