/************************************************************************* 
  > File Name: BFS.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<list> 
using namespace std; 
 
/* 邻接表存储有向图 */ 
class Graph 
{ 
  int V;            // 顶点的数量 
  list<int> *adj;       // 邻接表 
  void BFSUtil(int v, bool visited[]); 
public: 
  Graph(int V);        // 构造函数 
  void addEdge(int v, int w); // 向图中添加一条边 
  void BFS(int v);       // BFS遍历 
}; 
 
/***** 构造函数 *****/ 
Graph::Graph(int V) 
{ 
  this->V = V; 
  adj = new list<int>[V];   // 初始化V条链表 
} 
 
/* 添加边，构造邻接表 */ 
void Graph::addEdge(int v, int w) 
{ 
  adj[v].push_back(w);     // 将w加到v的list 
} 
 
/* 从顶点v出发广度优先搜索 */ 
void Graph::BFSUtil(int v, bool visited[]) 
{ 
  // BFS辅助队列 
  list<int> queue; 
 
  // 将当前顶点标记为已访问并压入队列 
  visited[v] = true; 
  queue.push_back(v); 
 
  list<int>::iterator i; 
 
  while(!queue.empty()) 
  { 
    // 出队 
    v = queue.front(); 
    cout << v << " "; 
    queue.pop_front(); 
 
    // 检测已出队的顶点s的所有邻接顶点 
    // 若存在尚未访问的邻接点，访问它并压入队列 
    for(i = adj[v].begin(); i!=adj[v].end(); ++i) 
    { 
      if(!visited[*i]) 
      { 
        visited[*i] = true; 
        queue.push_back(*i); 
      }  
    } 
  } 
} 
 
/** 广度优先搜索 **/ 
void Graph::BFS(int v) 
{ 
  // 初始化访问标记数组 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
   
  // 假设从给定顶点可以到达图的所有顶点 
  BFSUtil(v, visited); 
} 
 
/* 测试 */ 
int main() 
{ 
  // 创建图 
  Graph g(4); 
  g.addEdge(0, 1); 
  g.addEdge(0, 2); 
  g.addEdge(1, 2); 
  g.addEdge(2, 0); 
  g.addEdge(2, 3); 
  g.addEdge(3, 3); 
 
  cout << "Following is BFS Traversal (starting from vertex 2) \n"; 
  g.BFS(2); 
  cout << endl; 
 
  return 0; 
} 

bool visited[MAX_VERTEXT_NUM];  // 访问标记数组 
 
void BFS(Graph G)    // 设访问函数为visit() 
{ 
  for(i=0; i<G.vexnum; ++i) 
    visited[i] = false;   // 初始化 
  for(i=0; i<G.vexnum; ++i)  // 从0号顶点开始遍历 
    if(!visited[i])     // 对每个连通分量调用一次BFS 
      BFS(G,i);      // Vi未访问过，从Vi开始BFS 
} 
 
void BFSUtil(Graph G, int v) 
{ 
  visit(v);          // 访问初始顶点 
  visited[v] = true;      // v已访问 
  Enqueue(Q, v);        // 顶点v入队列 
  while(!isEmpty(Q)) 
  { 
    Dequeue(Q, v);      // 顶点v出队列 
    for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v)) 
      if(!visited[w])   // 检测v的所有邻接点 
      { 
        visit(w);    // 若w未访问，访问之 
        visited[w]=true; // 标记 
        Enqueue(Q, w);  // 顶点w入队列 
      } 
  } 
} 

void Graph::BFS() 
{ 
 // 初始化访问标记数组 
 bool *visited = new bool[V]; 
 for(int i=0; i<V; ++i) 
   visited[i] = false; 
  
 // 对每个连通分量调用一次BFSUtil()，从0号顶点开始遍历 
 for(int i=0; i<V; ++i) 
   if(!visited[i]) 
     BFSUtil(i, visited); 
} 

void Graph::addEdge(int v, int w) 
{ 
 adj[v].push_back(w);     // 将w加到v的list 
 adj[w].push_back(v); 
}