LeetCode 133 - Clone Gragh

作者 QIFAN 日期 2017-01-26
LeetCode 133 - Clone Gragh

原题链接: 133. Clone Graph


题干

给定无向图的节点,节点包含唯一的 label 与它的所有邻居。要求克隆出这个无向图。

节点的结构如下:

//Definition for undirected graph.
class UndirectedGraphNode {
int label;
List<UndirectedGraphNode> neighbors;
UndirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<UndirectedGraphNode>();
}
}

思路

可以 DFS 也可以 BFS ,用一个 HashMap<lable, Node> 来保存已经建立的节点。

BFS

  • 对于每个节点,连接所有邻居
    • 若邻居存在于 map ,直接连接
    • 若不存在,克隆邻居,连接,放入列表进行下一轮
    • 对新增加的邻居 BFS
  • base case 是新增列表为空

代码:

HashMap<Integer, UndirectedGraphNode> nodesMap = new HashMap<>();
Stack<UndirectedGraphNode> newNeighbors = new Stack<>();
Stack<UndirectedGraphNode> originNeighbors = new Stack<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
nodesMap.put(node.label, clone);
cloneGraph(node, clone);
return clone;
}
private void cloneGraph(UndirectedGraphNode origin, UndirectedGraphNode clone) {
for (UndirectedGraphNode neighbor: origin.neighbors) {
if (!nodesMap.containsKey(neighbor.label)) {
newNeighbors.push(new UndirectedGraphNode(neighbor.label));
originNeighbors.push(neighbor);
nodesMap.put(neighbor.label, newNeighbors.peek());
}
clone.neighbors.add(nodesMap.get(neighbor.label));
}
while (!newNeighbors.isEmpty()) {
cloneGraph(originNeighbors.pop(), newNeighbors.pop());
}
}

DFS

  • 对于节点 curr ,遍历邻居
    • 若邻居存在与 map,则只需增加关系
    • 若邻居不存在,则克隆邻居,并对邻居递归 DFS ,再增加关系
  • base case 是所有邻居都已经在 map 中,只需增加关系就跳出了。

代码:

HashMap<Integer, UndirectedGraphNode> nodesMap = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
UndirectedGraphNode cloneNode = new UndirectedGraphNode(node.label);
nodesMap.put(node.label, cloneNode);
DFSHelper(node, cloneNode);
return cloneNode;
}
private void DFSHelper(UndirectedGraphNode node, UndirectedGraphNode cloneNode) {
if (node == null) {
return;
}
if (node.neighbors.size() == 0) {
return;
}
for (UndirectedGraphNode neighbor: node.neighbors) {
if (!nodesMap.containsKey(neighbor.label)) {
UndirectedGraphNode cloneNeighbor = new UndirectedGraphNode(neighbor.label);
nodesMap.put(neighbor.label, cloneNeighbor);
DFSHelper(neighbor, cloneNeighbor);
}
cloneNode.neighbors.add(nodesMap.get(neighbor.label));
}
}

DFS 会比较快一些,而且不需要记录 neighbor 的引用。这一题重点思想是图的遍历,其他遍历差不多都是这样的变体。