首页 > 代码库 > leetcode Clone Graph

leetcode Clone Graph

2024-07-21 18:05:19   226人阅读

Clone Graph

 Total Accepted: 16482 Total Submissions: 72324My Submissions

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
         /          \_/

Have you been asked this question in an interview? 

Discuss

//首先，这种深拷贝的题目，需要有一个辅助工具来判断中的节点是否重复。本题是图的拷贝，按照某一个规律全部把图的节点全部遍历一遍。

//我是用map来判断是否重复，然后根据原图进行广度优先遍历，然后把新图的节点一一new出来，并对节点进行相应的连接。


<span style="font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px;">/**</span>
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
 //7:35->
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        map<UndirectedGraphNode *,UndirectedGraphNode *> repeat;
        // one set and two queue
        // store the original nodes and new nodes;que is for old graph. que2 is for new graph.
        queue<UndirectedGraphNode *> que;
        queue<UndirectedGraphNode *> que2;
        UndirectedGraphNode *head=NULL,*h1=NULL,*h2=NULL,*h3=NULL;
        int i=0,j=0;
        if(node==NULL)
        {
            return head;
        }
        que.push(node);
        h1=head = new UndirectedGraphNode(node->label);
        que2.push(h1);
        repeat[node] = h1;
        // begin bfs
        while(que.size()>0)
        {
            node = que.front();
            que.pop();
            h1 = que2.front();
            que2.pop();
            for(i=0;i<node->neighbors.size();i++)
            {
                h2 = node->neighbors[i];
                if(repeat.count(h2)==0)
                {
                    h3 = new UndirectedGraphNode(h2->label);
                    h1->neighbors.push_back(h3);
                    repeat[h2] = h3;
                    que.push(h2);
                    que2.push(h3);
                }else
                {
<span style="white-space:pre">		</span>//add the new link in new graph
                    h1->neighbors.push_back(repeat[h2]);
                }
            }
        }
        return head;
    }
};


leetcode Clone Graph


联系
我们