why such a code "Memory Limit Exceeded"?

Question

"Clone Graph" /* *I used BFS to traverse the whole graph, a queue to store the neighbor, which will be accessed next loop *mapGraph to store the created node. map <label, UndirectedGraphNode *> * */ ----------------------my code-----------------------------

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    queue<UndirectedGraphNode *> q;
    UndirectedGraphNode *source = NULL; // viariable stores the given graph node
    UndirectedGraphNode *root = NULL;
    map<int, UndirectedGraphNode *>mapGraph;//store the cloned node <label, UndirectedGraphNode *>
    vector<UndirectedGraphNode *> neighbors; //for convenience, stores the neighbors from source.
    int is_first = 1, i, size;

    if(node == NULL)
        return root;

    q.push(node);//store the first node;
    while(!q.empty())
    {
        source = q.front();
        UndirectedGraphNode *target = new UndirectedGraphNode(source -> label);
        mapGraph[source -> label] = target;

        if(is_first)// just store the root, which is returned value in future
        {
            root = target;
            is_first = 0;
        }
        neighbors = source -> neighbors;//store the neighbor from source, just for convenient to use in the next
        size = neighbors.size();
        for(i = 0; i < size; i++)//traversing the neighbors
        {
            // weather  the node is created already, here using the map to store the created node
            // if the node is not in map, just create it and label it, add it in the map.
            if(mapGraph.find(neighbors[i] -> label) == mapGraph.end())
            {
                UndirectedGraphNode *tmp = new UndirectedGraphNode(neighbors[i] -> label);
                mapGraph[tmp -> label] = tmp;
                (target -> neighbors).push_back(tmp);
            }
            else//
            {
                (target -> neighbors).push_back(mapGraph[neighbors[i] -> label]);
            }
            q.push(neighbors[i]);
        }

        q.pop();
    }
    return root;
}

Comments

Could you tell algorithm in some words and add some comment in your code?

---

already add some comments, thank you for your attention. I really want to know the reason~ I have cost 2 hours to debug and think of the MLE, no clues still.

Answer 1

You are pushing each of the neighbors into the queue, which is a bad idea. You only want to push a neighbor node into the queue only when the neighbor node is not a node you have visited before.

Why? Because the graph could contain cycles and you want to prevent that in your cloning process.

The other problem with your solution is the following line:

UndirectedGraphNode *target = new UndirectedGraphNode(source -> label);

Imagine your algorithm finish cloning all neighbors (nodes A, B, C) of the starting node into nodes A', B', and C'. It retrieves the next element from the queue which is node A'. And your above code basically clone A' again to A''. Did you see the problem? You are storing the references of neighbors of A into A'', while it should be stored into A'.

Comments

You are correct!!! Thank you very much, I solved the aboved problem according to your advice. first , I moved the queue:

             if(mapGraph.find(neighbors[i] -> label) == mapGraph.end())

            {
                UndirectedGraphNode *tmp = new UndirectedGraphNode(neighbors[i] -> label);

                mapGraph[tmp -> label] = tmp;

                (target -> neighbors).push_back(tmp);

                q2.push(tmp);

                q1.push(neighbors[i]);

            }

second, I added another queue q2 to store newly created node, that is target. anyway , the problem is accepted. Thank you again!