Friday, March 7, 2014

Graph BFS traverse

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