欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

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

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

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

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

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

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

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

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

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

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

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

/************************************************************************* 
  > 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)記為已訪問(wèn)并壓入隊(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) 
    // 若存在尚未訪問(wèn)的鄰接點(diǎn)，訪問(wè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) 
{ 
  // 初始化訪問(wèn)標(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; 
}

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

偽代碼如下：

bool visited[MAX_VERTEXT_NUM];  // 訪問(wèn)標(biāo)記數(shù)組 
 
void BFS(Graph G)    // 設(shè)訪問(wèn)函數(shù)為visit() 
{ 
  for(i=0; i<G.vexnum; ++i) 
    visited[i] = false;   // 初始化 
  for(i=0; i<G.vexnum; ++i)  // 從0號(hào)頂點(diǎn)開(kāi)始遍歷 
    if(!visited[i])     // 對(duì)每個(gè)連通分量調(diào)用一次BFS 
      BFS(G,i);      // Vi未訪問(wèn)過(guò)，從Vi開(kāi)始BFS 
} 
 
void BFSUtil(Graph G, int v) 
{ 
  visit(v);          // 訪問(wèn)初始頂點(diǎn) 
  visited[v] = true;      // v已訪問(wèn) 
  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未訪問(wèn)，訪問(wèn)之 
        visited[w]=true; // 標(biāo)記 
        Enqueue(Q, w);  // 頂點(diǎn)w入隊(duì)列 
      } 
  } 
}

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

void Graph::BFS() 
{ 
 // 初始化訪問(wèn)標(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)開(kāi)始遍歷 
 for(int i=0; i<V; ++i) 
   if(!visited[i]) 
     BFSUtil(i, visited); 
}

對(duì)于無(wú)向圖的廣度優(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ù)雜度

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

2 . 時(shí)間復(fù)雜度

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

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

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

相關(guān)文章

最新評(píng)論