What is the best way to solve Clone Graph?

The optimized O(1) approach using Graphs patterns is generally preferred.

상위 150개 인터뷰중간

그래프 복제

'복제 그래프' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

중간

연결된 무방향 그래프의 노드 참조가 주어지면 그래프의 전체 복사본(클론)을 반환합니다.

그래프의 각 노드에는 값(int)과 이웃 목록(List[Node])이 포함되어 있습니다.

그래프는 인접 목록으로 표현됩니다. adjList[i]가 노드 i+1(1-인덱스)의 이웃을 나타내는 cloneGraph(adjList: List[List[int]]) -> List[List[int]] 함수를 구현하세요. 복제된 그래프의 인접 목록을 반환합니다.

제약

•The number of nodes in the graph is in the range [0, 100]
•1 <= Node.val <= 100
•Node.val is unique for each node
•There are no repeated edges and no self-loops in the graph

예

Example 1

Input

adjList = [[2,4],[1,3],[2,4],[1,3]]

Output

[[2,4],[1,3],[2,4],[1,3]]

Explanation

Node 1's neighbors are 2 and 4. Node 2's neighbors are 1 and 3. Node 3's neighbors are 2 and 4. Node 4's neighbors are 1 and 3.

Example 2

Input

adjList = [[]]

Output

[[]]

Explanation

The graph contains only one node with value 1 and no neighbors.

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def clone_graph_opt(node):
    return clone_graph_brute(node)

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph_brute(node):
    if not node: return None
    oldToNew = {}
    def dfs(node):
        if node in oldToNew: return oldToNew[node]
        copy = Node(node.val)
        oldToNew[node] = copy
        for nei in node.neighbors:
            copy.neighbors.append(dfs(nei))
        return copy
    return dfs(node)