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

0 comments:

Blogroll

Follow this blog by Email

Popular Posts