Using BFS method to traverse a graph.
Answer:
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* bool visited;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x), visited(false) {};
* }
**/
class Solution{
public:
vector<UndirectedGraphNode *> bfs (UndirectedGraphNode* node){
queue<UndirectedGraphNode*> que;
vector<UndirectedGraphNode*> res;
que.push(node);
while(!que.empty()){
UnidirectedGraphNode *cur = que.top();
que.pop();
res.push_back(cur);
for(int i=0; i < cur->neighbors.size();++i){
UndirectedGraphNode* nb= cur->neighbor[i];
if(!nb->visited){
que.push(nb);
nb->visited=true;
}
}
}
return res;
}
};
No comments:
Post a Comment