【Lintcode】137. Clone Graph

Shirley ·

更新时间:2024-11-14

· 762 次阅读

题目地址：

https://www.lintcode.com/problem/clone-graph/description

Deep copy一个图。图以邻接表方式存储。

思路是，先从给定的顶点出发，搜索到图中的所有的顶点，然后为每个顶点创建一份拷贝；接着，遍历原图的顶点，每遍历一个点的时候，就得到其邻居节点，将这个邻居关系赋予给对应的顶点。全部遍历完的时候直接返回即可。遍历原图的顶点的方式可以用BFS。代码如下：

import java.util.*;
public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        // write your code here
        // 判空
        if (node == null) {
            return null;
        }
        // 得到原图中的所有顶点
        List nodes = getNodes(node);
        // 存储原图的顶点和新new出来的图的顶点的一一对应关系
        Map map = new HashMap();
        // 遍历原图中的顶点，为原图的顶点和新图的对应顶点建立映射关系
        for (UndirectedGraphNode n : nodes) {
            map.put(n, new UndirectedGraphNode(n.label));
        }
    	// 遍历原图的顶点，得到新图中对应的顶点，然后得到原图顶点的所有邻居，
    	// 再得到新图中对应顶点的所有邻居，接着将这些邻居关系保存起来
        for (UndirectedGraphNode n : nodes) {
            UndirectedGraphNode newNode = map.get(n);
            for (UndirectedGraphNode neighbor : n.neighbors) {
                UndirectedGraphNode newNeighbor = map.get(neighbor);
                newNode.neighbors.add(newNeighbor);
            }
        }
        return map.get(node);
    }
    private List getNodes(UndirectedGraphNode node) {
        Queue queue = new LinkedList();
        Set visited = new HashSet();
        queue.offer(node);
        visited.add(node);
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            for (UndirectedGraphNode neighbor : cur.neighbors) {
                if (visited.add(neighbor)) {
                    queue.offer(neighbor);
                }
            }
        }
        return new ArrayList(visited);
    }
}
class UndirectedGraphNode {
    int label;
    List neighbors;
    UndirectedGraphNode(int x) {
        label = x;
        neighbors = new ArrayList();
    }
}

时空复杂度O(n)O(n)O(n)。

作者：记录算法

clone

1024 个赞