Cloning a graph

Cloning a graph

240px-Undirected_graph_for_adjacencylist.svg_

Cloning a graph is one of the easier problems. A quick code demonstrates this …

import java.util.*;

public class CloneGraph {
    public class Node{
        int val = 0;
        List neighbors = null;
        public Node(int val, List neighbors){
            this.val = val;
            this.neighbors = neighbors;
        }
    }
    public Node cloneGraph(Node node) {
        return duplicate(node);
    }
    Map<Node, Node> visited = new HashMap();
    private Node duplicate(Node n){
        List<Node> dup_children = new ArrayList();
        Node dupl = new Node(n.val, dup_children);
        if(visited.containsKey(n)){
            return visited.get(n);
        }else{
            visited.put(n, dupl);
            if(n.neighbors!=null){
                dup_children = dupl.neighbors;
                for(Object child: n.neighbors){
                    Node dup_child = duplicate((Node)child);
                    dup_children.add(dup_child);
                }
            }
        }
        return dupl;
    }
}
Advertisements
READ  Code to tell if a binary tree is balanced

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Terms of Use | Privacy Policy 
2018-2019 © eXitDiscount