/************************************************************************* 
  > File Name: BFS.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<list> 
using namespace std; 
 
/* 鄰接表存儲(chǔ)有向圖 */ 
class Graph 
{ 
  int V;            // 頂點(diǎn)的數(shù)量 
  list<int> *adj;       // 鄰接表 
  void BFSUtil(int v, bool visited[]); 
public: 
  Graph(int V);        // 構(gòu)造函數(shù) 
  void addEdge(int v, int w); // 向圖中添加一條邊 
  void BFS(int v);       // BFS遍歷 
}; 
 
/***** 構(gòu)造函數(shù) *****/ 
Graph::Graph(int V) 
{ 
  this->V = V; 
  adj = new list<int>[V];   // 初始化V條鏈表 
} 
 
/* 添加邊，構(gòu)造鄰接表 */ 
void Graph::addEdge(int v, int w) 
{ 
  adj[v].push_back(w);     // 將w加到v的list 
} 
 
/* 從頂點(diǎn)v出發(fā)廣度優(yōu)先搜索 */ 
void Graph::BFSUtil(int v, bool visited[]) 
{ 
  // BFS輔助隊(duì)列 
  list<int> queue; 
 
  // 將當(dāng)前頂點(diǎn)標(biāo)記為已訪問并壓入隊(duì)列 
  visited[v] = true; 
  queue.push_back(v); 
 
  list<int>::iterator i; 
 
  while(!queue.empty()) 
  { 
    // 出隊(duì) 
    v = queue.front(); 
    cout << v << " "; 
    queue.pop_front(); 
 
    // 檢測(cè)已出隊(duì)的頂點(diǎn)s的所有鄰接頂點(diǎn) 
    // 若存在尚未訪問的鄰接點(diǎn)，訪問它并壓入隊(duì)列 
    for(i = adj[v].begin(); i!=adj[v].end(); ++i) 
    { 
      if(!visited[*i]) 
      { 
        visited[*i] = true; 
        queue.push_back(*i); 
      }  
    } 
  } 
} 
 
/** 廣度優(yōu)先搜索 **/ 
void Graph::BFS(int v) 
{ 
  // 初始化訪問標(biāo)記數(shù)組 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
   
  // 假設(shè)從給定頂點(diǎn)可以到達(dá)圖的所有頂點(diǎn) 
  BFSUtil(v, visited); 
} 
 
/* 測(cè)試 */ 
int main() 
{ 
  // 創(chuàng)建圖 
  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];  // 訪問標(biāo)記數(shù)組 
 
void BFS(Graph G)    // 設(shè)訪問函數(shù)為visit() 
{ 
  for(i=0; i<G.vexnum; ++i) 
    visited[i] = false;   // 初始化 
  for(i=0; i<G.vexnum; ++i)  // 從0號(hào)頂點(diǎn)開始遍歷 
    if(!visited[i])     // 對(duì)每個(gè)連通分量調(diào)用一次BFS 
      BFS(G,i);      // Vi未訪問過，從Vi開始BFS 
} 
 
void BFSUtil(Graph G, int v) 
{ 
  visit(v);          // 訪問初始頂點(diǎn) 
  visited[v] = true;      // v已訪問 
  Enqueue(Q, v);        // 頂點(diǎn)v入隊(duì)列 
  while(!isEmpty(Q)) 
  { 
    Dequeue(Q, v);      // 頂點(diǎn)v出隊(duì)列 
    for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v)) 
      if(!visited[w])   // 檢測(cè)v的所有鄰接點(diǎn) 
      { 
        visit(w);    // 若w未訪問，訪問之 
        visited[w]=true; // 標(biāo)記 
        Enqueue(Q, w);  // 頂點(diǎn)w入隊(duì)列 
      } 
  } 
} 

void Graph::BFS() 
{ 
 // 初始化訪問標(biāo)記數(shù)組 
 bool *visited = new bool[V]; 
 for(int i=0; i<V; ++i) 
   visited[i] = false; 
  
 // 對(duì)每個(gè)連通分量調(diào)用一次BFSUtil()，從0號(hào)頂點(diǎn)開始遍歷 
 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); 
}