亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C++實現(xiàn)廣度優(yōu)先搜索實例

 更新時間：2014年08月14日 12:05:27   投稿：shichen2014  
這篇文章主要介紹了C++實現(xiàn)廣度優(yōu)先搜索,對于C++程序員來說非常有借鑒價值,需要的朋友可以參考下

本文主要敘述了圖的遍歷算法中的廣度優(yōu)先搜索（Breadth-First-Search）算法，是非常經(jīng)典的算法，可供C++程序員參考借鑒之用。具體如下：

首先，圖的遍歷是指從圖中的某一個頂點出發(fā)，按照某種搜索方法沿著圖中的邊對圖中的所有頂點訪問一次且僅訪問一次。注意到樹是一種特殊的圖，所以樹的遍歷實際上也可以看作是一種特殊的圖的遍歷。圖的遍歷主要有兩種算法：廣度優(yōu)先搜索（Breadth-First-Search）和深度優(yōu)先搜索（Depth-First-Search）。

一、廣度優(yōu)先搜索（BFS）的算法思想

廣度優(yōu)先搜索類似于二叉樹的層序遍歷，它的基本思想就是：首先訪問起始頂點v，接著由v出發(fā)，依次訪問v的各個未訪問過的鄰接頂點w1，w2，…，wi，然后再依次訪問w1，w2，…，wi的所有未被訪問過的鄰接頂點；再從這些訪問過的頂點出發(fā)，再訪問它們所有未被訪問過的鄰接頂點……依次類推，直到圖中所有頂點都被訪問過為止。

廣度優(yōu)先搜索是一種分層的查找過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有往回退的情況，因此它不是一個遞歸的算法。為了實現(xiàn)逐層的訪問，算法必須借助一個輔助隊列，以記錄正在訪問的頂點的下一層頂點。

如上圖所示，為一個有向圖，從頂點2開始廣度優(yōu)先遍歷整個圖，可知結(jié)果為2，0，3，1。

二、BFS算法實現(xiàn)

與樹相比，圖的不同之處在于它存在回路/環(huán)，因此在遍歷時一個頂點可能被訪問多次。為了防止這種情況出現(xiàn)，我們使用一個訪問標(biāo)記數(shù)組visited[]來標(biāo)記頂點是否已經(jīng)被訪問過。

在廣度優(yōu)先搜索一個圖之前，我們首先要構(gòu)造一個圖，圖的存儲方式主要有兩種：鄰接矩陣、鄰接表。這里我們使用鄰接表來存儲圖：

簡單起見，我們先假設(shè)從起始頂點可以達(dá)到其他所有頂點。以有向圖為例，C++代碼實現(xiàn)：

/************************************************************************* 
  > File Name: BFS.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<list> 
using namespace std; 
 
/* 鄰接表存儲有向圖 */ 
class Graph 
{ 
  int V;            // 頂點的數(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 
} 
 
/* 從頂點v出發(fā)廣度優(yōu)先搜索 */ 
void Graph::BFSUtil(int v, bool visited[]) 
{ 
  // BFS輔助隊列 
  list<int> queue; 
 
  // 將當(dāng)前頂點標(biāo)記為已訪問并壓入隊列 
  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); 
      }  
    } 
  } 
} 
 
/** 廣度優(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è)從給定頂點可以到達(dá)圖的所有頂點 
  BFSUtil(v, visited); 
} 
 
/* 測試 */ 
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; 
}

上面是假設(shè)從起始頂點開始能夠訪問到圖的所有頂點。如果不能到達(dá)所有頂點，即存在多個連通分量呢？那么我們就要對每個連通分量都進(jìn)行一次廣度優(yōu)先搜索。

偽代碼如下：

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號頂點開始遍歷 
    if(!visited[i])     // 對每個連通分量調(diào)用一次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; // 標(biāo)記 
        Enqueue(Q, w);  // 頂點w入隊列 
      } 
  } 
}

根據(jù)偽代碼，相信不難寫出對于多個連通分量的圖的廣度優(yōu)先搜索。我們只需要修改BFS()函數(shù)部分：

void Graph::BFS() 
{ 
 // 初始化訪問標(biāo)記數(shù)組 
 bool *visited = new bool[V]; 
 for(int i=0; i<V; ++i) 
   visited[i] = false; 
  
 // 對每個連通分量調(diào)用一次BFSUtil()，從0號頂點開始遍歷 
 for(int i=0; i<V; ++i) 
   if(!visited[i]) 
     BFSUtil(i, visited); 
}

對于無向圖的廣度優(yōu)先搜索，只是鄰接表不一樣，其他的都是一樣的。我們只需要修改addEdge(v, w)函數(shù)：

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

三、BFS算法性能分析

1 . 空間復(fù)雜度

無論是鄰接表還是鄰接矩陣的存儲方式，BFS算法都需要借助一個輔助隊列Q，n個頂點都需要入隊一次，在最壞的情況下，空間復(fù)雜度為O(|V|)。

2 . 時間復(fù)雜度

當(dāng)采用鄰接表存儲時，每個頂點均需搜索一次，故時間復(fù)雜度為O(|V|)，在搜索任一頂點的鄰接點時，每條邊至少訪問一次，故時間復(fù)雜度為O(|E|)，算法總的時間復(fù)雜度為O(|V|+|E|)。

當(dāng)采用鄰接矩陣存儲時，查找每個頂點的鄰接點所需的時間為O(|V|)，故算法總的時間復(fù)雜度為O(|V|^2)。

注：廣度優(yōu)先搜索（BFS）算法思想有很多應(yīng)用，比如Dijkstra單源最短路徑算法和Prim最小生成樹算法。

相關(guān)文章

最新評論