Clone Graph

Clone Graph

 

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

OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/ 

Naive Way:难点在于穿件了新的节点如何找回原来对应的节点，并且输入只有一个节点。

用Map可以正中下怀的解决这个问题。

算法复杂度是O(n),space是O(n)。 

/**

 * Definition for undirected graph.

 * class UndirectedGraphNode {

 *     int label;

 *     List<UndirectedGraphNode> neighbors;

 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

 * };

 */

public class Solution {

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

        Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>();

        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();

        if(node==null){return null;}

        // BFS, give every node a clone, put relationship into a map

        UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);

        map.put(node,newHead);

        queue.add(node);

        while(!queue.isEmpty()){

            UndirectedGraphNode temp = queue.poll();

            for(int i = 0;i < temp.neighbors.size();i++){

                if(!map.containsKey(temp.neighbors.get(i))){

                    queue.add(temp.neighbors.get(i));

                    UndirectedGraphNode newNode = new UndirectedGraphNode(temp.neighbors.get(i).label);

                    map.put(temp.neighbors.get(i),newNode);

                }

            }

        }

        // according to the map, construct new graph

        queue.add(node);

        set.add(node);

        while(!queue.isEmpty()){

            UndirectedGraphNode temp = queue.poll();

            if(!map.containsKey(temp)){return null;}

            UndirectedGraphNode clone = map.get(temp);

            for(int i = 0;i < temp.neighbors.size();i++){

                if(!map.containsKey(temp.neighbors.get(i))){return null;}

                clone.neighbors.add(map.get(temp.neighbors.get(i)));

                if(!set.contains(temp.neighbors.get(i))){

                    set.add(temp.neighbors.get(i));

                    queue.add(temp.neighbors.get(i));

                }

            }

        }

        return map.containsKey(node)?map.get(node):null;

    }

}

 

Improves Way: 后来，我根据Copy list with random pointer里看别人的一个算法，想到可以套用过来，在每隔节点的最后增加一个新的neighbor，然后将每个节点的最后一个neighbor指向他所有neighbor的最后一个neighbor。

 

这样子不需要额外的空间存关系，但是遍历的原因还是要O(n)的space。

 

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null){return null;}
       
        // create a new Node with the same label put it as the last neighbor for the original node
        ArrayList<Integer> table = new ArrayList<Integer>();
        UndirectedGraphNode cur = node;
        UndirectedGraphNode rslt = null;
        Stack<UndirectedGraphNode> s = new Stack<UndirectedGraphNode>();
        s.push(node);
        while(!s.isEmpty()){
            cur = s.pop();
            if(!table.contains(cur.label)){
                table.add(cur.label);
                for(int i = 0;i < cur.neighbors.size();i++){
                    if(!table.contains(cur.neighbors.get(i).label)){
                        s.push(cur.neighbors.get(i));
                    }
                }
                UndirectedGraphNode newNode = new UndirectedGraphNode(cur.label);
                cur.neighbors.add(newNode);
            }
        }
       
        // assign relationship for the new nodes
        UndirectedGraphNode temp = null;
        table.clear();
        s.push(node);
        while(!s.isEmpty()){
            cur = s.pop();
            if(!table.contains(cur.label)){
                table.add(cur.label);
                for(int i = 0;i < cur.neighbors.size()-1;i++){
                    temp = cur.neighbors.get(i);
                    cur.neighbors.get(cur.neighbors.size()-1).neighbors.add(temp.neighbors.get(temp.neighbors.size()-1));
                    s.push(temp);
                }
            }
        }
       
        rslt = node.neighbors.get(node.neighbors.size()-1);
       
        // delete the relationship between original nodes and new nodes
        table.clear();
        s.push(node);
        while(!s.isEmpty()){
            cur = s.pop();
            if(!table.contains(cur.label)){
                table.add(cur.label);
                cur.neighbors.remove(cur.neighbors.size() - 1);
                for(int i = 0;i < cur.neighbors.size();i++){
                    s.push(cur.neighbors.get(i));
                }
            }
        }
       
        return rslt;
    }