leetCode-133:Clone Graph

问题描述

给定一个无向连通图，要求将图进行深拷贝。题目链接：**点我**

问题解法

使用深搜算法遍历每个节点，为了保证遍历过程中邻节点的正确性，将已经访问过的节点存在数组中，后续查找邻节点时直接从数组中进行获取，这样既能保证节点的正确性，也能提高访问效率。代码如下

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution
{
    public Node cloneGraph(Node node)
    {
        if (node == null)
        {
            return node;
        }

        Node[] nodes = new Node[101];
        copy(node, nodes, new boolean[101]);
        return nodes[node.val];
    }

    private void copy(Node source, Node[] nodes, boolean[] visited)
    {
        if (visited[source.val])
        {
            return;
        }

        visited[source.val] = true;
        if (nodes[source.val] == null)
        {
            nodes[source.val] = new Node(source.val, new ArrayList<>());
        }

        Node dest = nodes[source.val];
        for (Node neighbor : source.neighbors)
        {
            copy(neighbor, nodes, visited);
            dest.neighbors.add(nodes[neighbor.val]);
        }
    }
}