[LeetCode] 133. Clone Graph

轉自LeetCode

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

<Solution>
這題的題意其實就是要做 deep copy，即要完整複製一份 undirected graph

有DFS和BFS兩種解法，這次使用 DFS 來解

想法如下

• 因為題目有說，每個 label 都是唯一的，所以使用一個 hash map 來記錄已經創好的 node，避免創建出多餘的node

• 用 DFS 去處理 neighbors 的拷貝。先把一條完整的 path 串完，再回頭找下一條

code 如下(參考資料)
c++

	/**
	* Definition for undirected graph.
	* struct UndirectedGraphNode {
	* int label;
	* vector<UndirectedGraphNode *> neighbors;
	* UndirectedGraphNode(int x) : label(x) {};
	* };
	*/
	class Solution {
	private:
	unordered_map<int, UndirectedGraphNode *> nodeMap;
	public:
	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
	return deepCopy(node);
	}
	UndirectedGraphNode *deepCopy(UndirectedGraphNode *node) {
	if(!node) {
	return NULL;
	}
	else if(nodeMap.count(node->label)) {
	return nodeMap[node->label];
	}
	UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
	nodeMap[node->label] = newNode;
	//>> copy neighbors by using DFS
	for(auto n : node->neighbors) {
	newNode->neighbors.push_back(deepCopy(n));
	}
	return newNode;
	}
	};

view raw deepCopyUndirectedGraph.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Definition for a Node.
	* class Node(var `val`: Int) {
	* var neighbors: ArrayList<Node?> = ArrayList<Node?>()
	* }
	*/
	class Solution {
	private val map = mutableMapOf<Int,Node>()
	fun cloneGraph(node: Node?): Node? {
	return deepCopy(node)
	}
	fun deepCopy(node: Node?): Node? {
	if (node == null) {
	return null
	} else if(map.contains(node!!.`val`)) {
	return map[node!!.`val`]
	}
	val newNode = Node(node!!.`val`)
	map[node!!.`val`] = newNode
	for(n in node!!.neighbors) {
	newNode.neighbors.add(deepCopy(n))
	}
	return newNode
	}
	}

view raw clone_graph.kt hosted with ❤ by GitHub