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;
}

4 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
  2. Requirement for custom application development has risen today with increment in the quantity of PDA clients. custom javascript development company can enable organizations to connect with their customers in less demanding ways.

    ReplyDelete
  3. As Indicated by the Best video javascript development company As we probably am aware there is an eager market for gaming on the web, on handheld gadgets and consoles alike. Individuals who profit, however as we might find in the development and extension of Open source diversions the motivators and inspirations to grow are substantially less fulfilling, unless obviously you bolster testing Mac's one-sided nearness.

    ReplyDelete

Blogroll

Follow this blog by Email

Popular Posts