Clone an undirected graph.

Solution 1: BFS遍历图并复制点,再复制neighbors

 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if(node == null){
        return null;
    }
    Map<UndirectedGraphNode, UndirectedGraphNode> hashmap = new HashMap<>();
    Queue<UndirectedGraphNode> queue = new LinkedList<>();


    queue.offer(node);
    UndirectedGraphNode node1 = new UndirectedGraphNode(node.label);
    hashmap.put(node, node1);


    while(!queue.isEmpty()){
        UndirectedGraphNode newnode = queue.poll();
        for(UndirectedGraphNode neighbour: newnode.neighbors){
            if(hashmap.containsKey(neighbour)){
                 continue;
            }
            queue.offer(neighbour);
            UndirectedGraphNode node2 = new UndirectedGraphNode(neighbour.label);
            hashmap.put(neighbour, node2);
        }    
    }

    for(Map.Entry<UndirectedGraphNode, UndirectedGraphNode> entry : hashmap.entrySet()){
        UndirectedGraphNode node3 = entry.getKey();
        UndirectedGraphNode node4 = entry.getValue();
        for(UndirectedGraphNode neighbour: node3.neighbors){
            node4.neighbors.add(hashmap.get(neighbour));
        }
    }
    return node1;
 }

Solution 2: DFS

更好的DFS:

results matching ""

    No results matching ""