133. Clone Graph - cocoder39/coco39_LC GitHub Wiki

133. Clone Graph

Notes 2020:

bfs

• one of clone's purpose is to be used as visited set to prevent revisiting a node
• every node is cloned before enqueuing

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return node

        queue = collections.deque([node])
        visited = {node: Node(node.val)}

        while queue:
            old = queue.popleft()
            for old_neighbor in old.neighbors:
                if old_neighbor not in visited:
                    visited[old_neighbor] = Node(old_neighbor.val)
                    queue.append(old_neighbor)
                visited[old].neighbors.append(visited[old_neighbor])
        return visited[node]

dfs

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        

        def dfs(node, visited):
            if not node:
                return 
            
            if node not in visited:
                visited[node] = Node(node.val) #1, 2, 3
                for neighbor in node.neighbors: #4 / 3 / 4 
                    if neighbor not in visited:
                        dfs(neighbor, visited)
                    visited[node].neighbors.append(visited[neighbor])

        if not node:
            return node
        visited = {}
        dfs(node, visited)
        return visited[node]

============================================================================================================ basic idea is same as copy linked list: traversal -> create, mapping -> link

traversal a graph: bfs + queue + unordered_set

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (! node) return nullptr;
        
        //create new nodes by bfs+queue
        unordered_set<UndirectedGraphNode*> visited;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
        
        queue<UndirectedGraphNode*> qu1;
        qu1.push(node);
        while (! qu1.empty()) {
            UndirectedGraphNode* original = qu1.front();
            qu1.pop();
            visited.insert(original);
            
            UndirectedGraphNode* copy = new UndirectedGraphNode(original->label);
            mp[original] = copy;
            
            for (auto neighbor : original->neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    qu1.push(neighbor);
                }
            }
        }
        
        //make connection
        for (auto original : visited) {
            for (auto neighbor : original->neighbors) {
                mp[original]->neighbors.push_back(mp[neighbor]);
            }
        }
        return mp[node];
    }

an optimization is linking when traversal.

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (! node) return nullptr;
        
        //create new nodes by bfs+queue
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
        mp[node] = new UndirectedGraphNode(node->label);
        
        queue<UndirectedGraphNode*> qu;
        unordered_set<UndirectedGraphNode*> visited;
        
        qu.push(node);
        visited.insert(node);
        while (! qu.empty()) {
            UndirectedGraphNode* original = qu.front();
            qu.pop();
            
            for (auto neighbor : original->neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    mp[neighbor] = new UndirectedGraphNode(neighbor->label);
                    qu.push(neighbor);
                    visited.insert(neighbor);
                }
                mp[original]->neighbors.push_back(mp[neighbor]);
            }
        }
        return mp[node];
    }

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map; // map original node to cloned node
        return helper(node, map);
    }
private:
    UndirectedGraphNode *helper(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *>& map){
        if (! node) {
            return nullptr;
        }
        
        if (map.find(node) == map.end()) { //haven't been updated 
            map[node] = new UndirectedGraphNode(node->label);
            for (auto neighbor : node->neighbors) {
                map[node]->neighbors.push_back(helper(neighbor, map));
            }
        }
        return map[node];
    }
};