# Clone Graph

## Question ([LC.133](https://leetcode.com/problems/clone-graph/?tab=Description))

> Given a node in undirected graph, clone this graph.

Return a node in the cloned (deep copy) graph.

## Analysis

Well we have to assume this graph is connected. Otherwise, there's no way to get to all vertices from the given vertex.

## BFS Approach

The question wants you to recreate an adjacency list with the given start node.

```
Step 1 explore the whole graph by BFS
to find all the vertices first
Step 2 Clone all vertices (label)
Map<oldVertex, clonedVertex>
Step 3 Clone all edges (neighbors)
for each node copy the edge
```

## Code

```java
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    // Step 1 Find all vertices
    Set<UndirectedGraphNode> verSet = new HashSet<>();
    exploreGraph(node, verSet);
    // Step 2 Deep copy nodes
    Map<UndirectedGraphNode, UndirectedGraphNode> mapOC = new HashMap<>();
    for (UndirectedGraphNode org : verSet) {
        UndirectedGraphNode copy = new UndirectedGraphNode(org.label);
        mapOC.put(org, copy);
    }
    // Step 3 Copy all the edges
    for (UndirectedGraphNode org : mapOC.keySet())
        for (UndirectedGraphNode orgEdge : org.neighbors)     
            mapOC.get(org).neighbors.add(mapOC.get(orgEdge));
    return mapOC.get(node);
}
```

Graph explore with DFS

```java
private void exploreGraph(UndirectedGraphNode start, Set<UndirectedGraphNode> verSet) {
    // stop search
    if (verSet.contains(start)) {
        return;
    }
    // previsit
    verSet.add(start);
    // depth first search
    for (UndirectedGraphNode neighbor : start.neighbors) {
        exploreGraph(neighbor, verSet);
    }
    // postvisit do nothing
}
```

Graph explore with BFS

```java
private void exploreGraph(UndirectedGraphNode start, Set<UndirectedGraphNode> verSet) {
    // init queue
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    queue.offer(start);
    verSet.add(start);
    // bfs
    UndirectedGraphNode current;
    while (!queue.isEmpty()) {
        current = queue.poll();
        for (UndirectedGraphNode neighbor : current.neighbors) {
            if (!verSet.contains(neighbor)) {
                queue.offer(neighbor);
                verSet.add(neighbor);
            }
        }
    }
}
```

## One-Go Approach

DFS is shorter to write because of the power of recursion. Just beware of the possible (call) stack overflow. We can intelligently utilize all the properties of DFS to produce the concise code below. During the previsit phrase, we can deep copy all the vertices. During backtracking, we can copy all the outgoing edges (neighbors) for that node using the base case to get the reference. When we are finished with the current node, we can return it to the previous node as a reference to its outgoing edge.

```java
public UndirectedGraphNode cloneGraph(UndirectedGraphNode start) {
    if (start == null) return start;
    Map<UndirectedGraphNode, UndirectedGraphNode> mapOC = new HashMap<>();
    return cloneDFS(start, mapOC);
}

private UndirectedGraphNode cloneDFS(UndirectedGraphNode current, 
                 Map<UndirectedGraphNode, UndirectedGraphNode> mapOC) {
    // base case 
    if (mapOC.containsKey(current)) {
        return mapOC.get(current); 
    }
    // pre visit deep copy the vertex
    UndirectedGraphNode currentCopy = new UndirectedGraphNode(current.label);
    mapOC.put(current, currentCopy);
    // DFS
    for (UndirectedGraphNode neighbor : current.neighbors) {
        // backtrack to copy all the outgoing edges
        currentCopy.neighbors.add(cloneDFS(neighbor, mapOC));
    }
    // post visit return the resolved vertex
    return mapOC.get(current);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/graph-search/graph-theory/graphthoery_md/clone-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.