LeetCode 133. 克隆圖（圖的BFS/DFS）

1. 題目

給定無向連通圖中一個節點的引用，傳回該圖的深拷貝（克隆）。圖中的每個節點都包含它的值 val（Int） 和其鄰居的清單（list[Node]）。

class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};           

複制

2. 解題

2.1 DFS

class Solution {
	Node* visited[101] = {NULL};
public:
    Node* cloneGraph(Node* node) {
        int size = node->neighbors.size();
        Node *root = new Node(node->val, vector<Node*> {});
        visited[node->val] = root;
        for (int i = 0; i < size; i++) {
            if (!visited[node->neighbors[i]->val])
                root->neighbors.push_back(cloneGraph(node->neighbors[i]));
            else
                root->neighbors.push_back(visited[node->neighbors[i]->val]);
        }
        return root;
    }
};           

複制

2.2 BFS

class Solution {
	bool visited[101] = {0};
public:
    Node* cloneGraph(Node* node) {
    	unordered_map<int, Node*> m;//新節點值和它自己的指針
    	unordered_map<Node*, vector<int>> nhb;//一個節點對應的鄰居的節點值
    	queue<Node*> q;
    	q.push(node);
    	Node *root, *ans;
    	visited[node->val] = 1;
    	int i = -1, n;
    	while(!q.empty())
    	{
    		n = q.front()->neighbors.size();
    		root = new Node(q.front()->val, vector<Node*> {});
    		if(i == -1)
    			ans = root;
    		m[q.front()->val] = root;
    		for(i = 0; i < n; i++)
    		{
    			nhb[root].push_back(q.front()->neighbors[i]->val);
    			if(!visited[q.front()->neighbors[i]->val])
    			{
    				q.push(q.front()->neighbors[i]);
    				visited[q.front()->neighbors[i]->val] = 1;
    			}
    		}
    		q.pop();
    	}
        for(auto it = nhb.begin(); it != nhb.end(); ++it)
        {
        	n = it->second.size();
        	for(i = 0; i < n; i++)
        	{
        		it->first->neighbors.push_back(m[it->second[i]]);
        	}
        }
        return ans;
    }
};           

複制