C++ BFS solution using two queue, and DFS solution


  • 0
    X

    BFS solution:

    class Solution {
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if (NULL == node) return NULL;
            unordered_map<int, UndirectedGraphNode *> labelToNode;
            queue<UndirectedGraphNode *> q1; //queue for original graph
            queue<UndirectedGraphNode *> q2; //queue for new graph
            
            UndirectedGraphNode * curNode = node;
            UndirectedGraphNode * newNode = new UndirectedGraphNode(curNode->label);
            UndirectedGraphNode * newHead = newNode;
            q1.push(curNode);
            q2.push(newNode);
            labelToNode[curNode->label] = newNode;
            
            while (!q1.empty()) {
                curNode = q1.front(); q1.pop();
                newNode = q2.front(); q2.pop();
                //iterate all curNode's neighbor list
                for (auto neighbor : curNode->neighbors) {
                    if (labelToNode.find(neighbor->label) == labelToNode.end()) {
                        UndirectedGraphNode * newNeighbor = new UndirectedGraphNode(neighbor->label);
                        newNode->neighbors.push_back(newNeighbor);
                        labelToNode[neighbor->label] = newNeighbor;
                        //enque
                        q1.push(neighbor);
                        q2.push(newNeighbor);
                    } else {//next neighbor's space has been allocated before
                        newNode->neighbors.push_back(labelToNode[neighbor->label]);
                    }
                }
            }
            
            return newHead;
        }
    };
    

    DFS solution:

    //DFS solution recursion
    class Solution {
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if (node == NULL) return NULL;
            UndirectedGraphNode * newNode = new UndirectedGraphNode(node->label);
            unordered_map<int, UndirectedGraphNode*> labelToNode;
            labelToNode[node->label] = newNode;
            dfs(node, newNode, labelToNode);
            return newNode;
        }
        
        void dfs(UndirectedGraphNode* curNode, UndirectedGraphNode* newNode, unordered_map<int, UndirectedGraphNode*>& labelToNode) {
            for (auto neighbor : curNode->neighbors) {
                if (labelToNode.find(neighbor->label) == labelToNode.end()) {
                    UndirectedGraphNode * newNeighbor = new UndirectedGraphNode(neighbor->label);
                    labelToNode[neighbor->label] = newNeighbor;
                    newNode->neighbors.push_back(newNeighbor);
                    dfs(neighbor, newNeighbor, labelToNode);
                } else {
                    newNode->neighbors.push_back(labelToNode[neighbor->label]);
                }
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.