leetCode-133:Clone Graph

问题描述

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

问题解法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
// 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]);
}
}
}