C++ BFS and DFS


  • 0
    /**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector<UndirectedGraphNode *> neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    class Solution {
    private:
        unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> hash;
    public:
        UndirectedGraphNode *cloneGraph_BFS(UndirectedGraphNode *node) {
            if(!node) return node;
            //unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> hash;
            UndirectedGraphNode *n = new UndirectedGraphNode(node->label);
            hash[node]=n;
            queue<UndirectedGraphNode*> q;
            q.push(node);
            while(!q.empty()) {
                UndirectedGraphNode *cur = q.front();
                q.pop();
                n = hash[cur];
                for(auto c:cur->neighbors) {
                    if(hash.count(c)==0) {
                        hash[c] = new UndirectedGraphNode(c->label);
                        q.push(c);
                    }
                    n->neighbors.push_back(hash[c]);
                }
            }
            return hash[node];
        }
        UndirectedGraphNode *cloneGraph_DFS(UndirectedGraphNode *node) {
            if(!node) return node;
            if(hash.count(node)>0) return hash[node];
            UndirectedGraphNode *cur = new UndirectedGraphNode(node->label);
            hash[node] = cur;
            for(auto n : node->neighbors) {
                cur->neighbors.push_back(cloneGraph(n));
            }
            return hash[node];
        }
    };
    

Log in to reply
 

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