题意：克隆一个用邻接矩阵表示的无向图。无向图的数据结构以及函数原型如下：
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { } };
解法：两遍BFS。第一遍把所有图的label找出来，用map<int,UndirectedGraphNode*>表示所有节点。第二遍把每个点的邻居找出来。要注意重边问题，不能再取队列的时候改变tag，要在放队列的时候改变tag，这样的话就能保证相同的节点不会被放2次。用tag蛮冗余的，其实再加邻居时，只要判断这个点的邻居是否为空就能保证不重复加邻居了。
代码如下：
/** * Definition for undirected graph. * struct UndirectedGraphNode { * int label; * vector<UndirectedGraphNode *> neighbors; * UndirectedGraphNode(int x) : label(x) {}; * }; */ class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { int i,j; UndirectedGraphNode * temp; queue<UndirectedGraphNode *> nodeQueue; map<int,UndirectedGraphNode *> ans; if(node==NULL) return NULL; nodeQueue.push(node); while(!nodeQueue.empty()) { temp=nodeQueue.front(); nodeQueue.pop(); ans[temp->label]=new UndirectedGraphNode(temp->label); for(i=0;i<temp->neighbors.size();i++) if(ans[temp->neighbors[i]->label]==NULL) nodeQueue.push(temp->neighbors[i]); } nodeQueue.push(node); while(!nodeQueue.empty()) { temp=nodeQueue.front(); nodeQueue.pop(); if(ans[temp->label]->neighbors.size()==0) { for(i=0;i<temp->neighbors.size();i++) { ans[temp->label]->neighbors.push_back(ans[temp->neighbors[i]->label]); nodeQueue.push(temp->neighbors[i]); } } } return ans[node->label]; } };
