首页 > 代码库 > Clone Graph

Clone Graph

2024-07-17 06:24:45   226人阅读

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

思路：使用BFS遍历无向图。使用map记录原始节点和新节点的地址映射，使用set记录已经完成复制操作的节点地址。

        查找map，确定是否需要对当前节点进行new操作，若是，对其进行new操作，并将地址映射存入map。

        查找set，确定是否已经完成了对当前节点的复制操作，若否，则表明需要更新其对应新节点的邻居信息。遍历当前节点的邻居向量，若某一邻居尚未被new出，则对其进行new操作，并将地址映射存入map，同时将新地址存入当前节点对应新节点的邻居向量中。

 1 class Solution { 2 public: 3     UndirectedGraphNode *cloneGraph( UndirectedGraphNode *node ) { 4         if( !node ) { return 0; } 5         list<UndirectedGraphNode*> nodeList; 6         unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> addrMap; 7         unordered_set<UndirectedGraphNode*> accessedSet; 8         nodeList.push_back( node ); 9         while( !nodeList.empty() ) {10             UndirectedGraphNode *newNode = 0, *curr = nodeList.front();11             nodeList.pop_front();12             if( addrMap.find( curr ) != addrMap.end() ) {13                 newNode = addrMap[curr];14             } else {15                 newNode = new UndirectedGraphNode( curr->label );16                 addrMap[curr] = newNode;17             }18             if( accessedSet.count( curr ) ) { continue; }19             for( size_t i = 0; i != curr->neighbors.size(); ++i ) {20                 UndirectedGraphNode *newNeighbor = 0, *neighbor = curr->neighbors[i];21                 if( addrMap.find( neighbor ) != addrMap.end() ) {22                     newNeighbor = addrMap[neighbor];23                 } else {24                     newNeighbor = new UndirectedGraphNode( neighbor->label );25                     addrMap[neighbor] = newNeighbor;26                 }27                 newNode->neighbors.push_back( newNeighbor );28                 nodeList.push_back( neighbor );29             }30             accessedSet.insert( curr );31         }32         return addrMap[node];33     }34 };

 


联系
我们