Problem

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

JavaScript Code

function UndirectedGraphNode(value, nebrs) {
    this.val = value;
    if(nebrs != null) {
        this.neighbors = nebrs; 
    } else {
        this.neighbors = [];
    }
    this.visited = false;
}

UndirectedGraphNode.prototype = {
        constructor: UndirectedGraphNode
}

function cloneGraph(node) {
    if(node == null)
        return null;

    var queue = [];
    var map = {};

    var newHead = new UndirectedGraphNode(node.val, node.neighbors);

    queue.push(node);
    map[node.val] = newHead;

    while(queue.length != 0){
        var curr = queue.shift();
        var currNeighbors = curr.neighbors; 

        for(var aNeighbor in currNeighbors){
            if(map[aNeighbor.val]==null){
                var copy = new UndirectedGraphNode(node.val, node.neighbors);
                map[aNeighbor.val] = copy;
                map[curr.val].neighbors.push(copy);
                queue.push(aNeighbor);
            }else{
                map[curr.val].neighbors.push(map[aNeighbor.val]);
            }
        }

    }
    return newHead;
}

2 comments:

  1. Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Front end developer learn from Javascript Training in Chennai . or learn thru JavaScript Online Training India. Nowadays JavaScript has tons of job opportunities on various vertical industry.

    ReplyDelete

Blogroll

Follow this blog by Email

Popular Posts