题目如下：实现克隆图的算法  

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

分析：BFS或者DFS遍历图，遍历的过程中复制节点，用哈希表保存新建立的节点的地址（同时这个哈希表可以用做节点访问标志）代码如下：                                                

1 /** 2  * Definition for undirected graph. 3  * struct UndirectedGraphNode { 4  *     int label; 5  *     vector
     
       neighbors; 6  *     UndirectedGraphNode(int x) : label(x) {}; 7  * }; 8  */ 9 class Solution {10 public:11     UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {12         // IMPORTANT: Please reset any member data you declared, as13         // the same Solution instance will be reused for each test case.14         typedef unordered_map
      
        Map;15         if(node == NULL)return NULL;16         Map gmap;//保存克隆图的节点的地址,顺便作为节点是否访问的标记17         stack
       
        gstack;18         UndirectedGraphNode *res = new UndirectedGraphNode(node->label);19         gmap.insert(Map::value_type(res->label, res));20         gstack.push(node);21         while(gstack.empty() == false)22         {23             UndirectedGraphNode *p = gstack.top(), *newp;24             gstack.pop();25             if(gmap.find(p->label) != gmap.end())//查找克隆图节点是否已经构造26                 newp = gmap[p->label];27             else28             {29                 newp = new UndirectedGraphNode(p->label);30                 gmap.insert(Map::value_type(p->label, newp));31             }32             for(int i = 0; i < p->neighbors.size(); i++)33             {34                 UndirectedGraphNode *tmp = p->neighbors[i];35                 if(gmap.find(tmp->label) == gmap.end())36                 {37                     gmap.insert(Map::value_type(tmp->label,38                                     new UndirectedGraphNode(tmp->label)));39                     gstack.push(tmp);40                 }41                 //设置克隆图节点的邻接点42                 newp->neighbors.push_back(gmap[tmp->label]);43             }44         }45         return res;46     }47 };
       
      
     

【版权声明】转载请注明出处：