C++实现广度优先搜索实例

本文主要叙述了图的遍历算法中的广度优先搜索(Breadth-First-Search)算法,是非常经典的算法,可供C++程序员参考借鉴之用。具体如下:

首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历。图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search)。

一、广度优先搜索(BFS)的算法思想

广度优先搜索类似于二叉树的层序遍历,它的基本思想就是:首先访问起始顶点v,接着由v出发,依次访问v的各个未访问过的邻接顶点w1,w2,…,wi,然后再依次访问w1,w2,…,wi的所有未被访问过的邻接顶点;再从这些访问过的顶点出发,再访问它们所有未被访问过的邻接顶点……依次类推,直到图中所有顶点都被访问过为止。

广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记录正在访问的顶点的下一层顶点。

如上图所示,为一个有向图,从顶点2开始广度优先遍历整个图,可知结果为2,0,3,1。

二、BFS算法实现

与树相比,图的不同之处在于它存在回路/环,因此在遍历时一个顶点可能被访问多次。为了防止这种情况出现,我们使用一个访问标记数组visited[]来标记顶点是否已经被访问过。

在广度优先搜索一个图之前,我们首先要构造一个图,图的存储方式主要有两种:邻接矩阵、邻接表。这里我们使用邻接表来存储图:

简单起见,我们先假设从起始顶点可以达到其他所有顶点。以有向图为例,C++代码实现:

/*************************************************************************
  > 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入队列
      }
  }
}

根据伪代码,相信不难写出对于多个连通分量的图的广度优先搜索。我们只需要修改BFS()函数部分:

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);
}

对于无向图的广度优先搜索,只是邻接表不一样,其他的都是一样的。我们只需要修改addEdge(v, w)函数:

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

三、BFS算法性能分析

1 . 空间复杂度

无论是邻接表还是邻接矩阵的存储方式,BFS算法都需要借助一个辅助队列Q,n个顶点都需要入队一次,在最坏的情况下,空间复杂度为O(|V|)。

2 . 时间复杂度

当采用邻接表存储时,每个顶点均需搜索一次,故时间复杂度为O(|V|),在搜索任一顶点的邻接点时,每条边至少访问一次,故时间复杂度为O(|E|),算法总的时间复杂度为O(|V|+|E|)。

当采用邻接矩阵存储时,查找每个顶点的邻接点所需的时间为O(|V|),故算法总的时间复杂度为O(|V|^2)。

注:广度优先搜索(BFS)算法思想有很多应用,比如Dijkstra单源最短路径算法和Prim最小生成树算法。

(0)

相关推荐

  • C++中虚函数与纯虚函数的用法

    本文较为深入的分析了C++中虚函数与纯虚函数的用法,对于学习和掌握面向对象程序设计来说是至关重要的.具体内容如下: 首先,面向对象程序设计(object-oriented programming)的核心思想是数据抽象.继承.动态绑定.通过数据抽象,可以使类的接口与实现分离,使用继承,可以更容易地定义与其他类相似但不完全相同的新类,使用动态绑定,可以在一定程度上忽略相似类的区别,而以统一的方式使用它们的对象. 虚函数的作用是实现多态性(Polymorphism),多态性是将接口与实现进行分离,采用

  • C++实现矩阵原地转置算法

    本文实例描述了C++实现矩阵原地转置算法,是一个非常经典的算法,相信对于学习C++算法的朋友有很大的帮助.具体如下: 一.问题描述 微软面试题:将一个MxN的矩阵存储在一个一维数组中,编程实现矩阵的转置. 要求:空间复杂度为O(1) 二.思路分析 下面以一个4x2的矩阵A={1,2,3,4,5,6,7,8}进行分析,转置过程如下图: 图中右下角的红色数字表示在一维数组中的下标.矩阵的转置其实就是数组中元素的移动,具体的移动过程如下图: 我们发现,这些移动的元素的下标是一个个环,下标1的元素移动到

  • C++线性时间的排序算法分析

    前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序(可以参考前一篇文章:各种内部排序算法的实现)等,这些排序算法都有一个共同的特点,就是基于比较. 本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序.它们将突破比较排序的Ω(nlgn)下界,以线性时间运行. 一.比较排序算法的时间下界 所谓的比较排序是指通过比较来决定元素间的相对次序. "定理:对于含n个元素的一个输入序列,

  • C++深度优先搜索的实现方法

    本文实例讲述了图的遍历中深度优先搜索的C++实现方法,是一种非常重要的算法,具体实现方法如下: 首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次.注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历.图的遍历主要有两种算法:广度优先搜索(Breadth-First-Search)和深度优先搜索(Depth-First-Search). 一.深度优先搜索(DFS)的算法思想 深度优先搜索算法所遵循的搜索策略是尽可能"深&

  • C++实现第K顺序统计量的求解方法

    一个n个元素组成的集合中,第K个顺序统计量(Order Statistic)指的是该集合中第K小的元素,我们这里要讨论的是如何在线性时间(linear time)里找出一个数组的第K个顺序统计量.该问题的算法对于C++程序员来说有一定的借鉴价值.具体如下: 一.问题描述: 问题:给定一个含有n个元素的无序数组,找出第k小的元素. k = 1 :最小值 k = n :最大值 k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ :中位数 找最大值或最小值很简单,只需要遍历一次数组并记录下最大值或最

  • C++继承中的访问控制实例分析

    本文较为深入的探讨了C++继承中的访问控制,对深入掌握C++面向对象程序设计是非常必要的.具体内容如下: 通常来说,我们认为一个类有两种不同的用户:普通用户 和 类的实现者.其中,普通用户编写的代码使用类的对象,这部分代码只能访问类的公有(接口)成员:实现者则负责编写类的成员和友元的代码,成员和友元既能访问类的公有部分,也能访问类的私有部分.如果进一步考虑继承的话就会出现第三种用户,即派生类.派生类可以访问基类的公有(public)成员和受保护(protected)成员,但不能访问基类的私有(p

  • C++变位词问题分析

    在<编程珠玑>一书的第二章提到了一个变位词问题,变位词指的是一个单词可以通过改变其他单词中字母的顺序来得到,也叫做兄弟单词,如army->mary.由变位词可以引申出几个算法问题,包括字符串包含问题,比较两个字符串是否是变位词,以及找出字典中变位词集合的问题. 一.字符串包含问题 (1) 问题描述:存在字符串1和字符串2,假设字符串2相对较短,如何快速地判定字符串2中的字符都存在于字符串1里(假定字符串只包含字母)? (2) 举例:字符串1为ABCDEFGHIJK,字符串2为ABCDE,

  • C++与C的差异分析

    虽说C++是向后兼容C的,但C++与C还是存在许多差异.本文列举了几个例子加以说明,同时这些也是我们非常容易忽略的地方.本文仅简单的列举几例,更多的不同之处读者还需要在学习与实践中不断的进行发掘和总结. C编译通过但C++编译不通过: 1.C++中编译器不允许在一个函数声明之前调用它,但C中编译器是允许的. #include<stdio.h> // 请用gcc和g++分别进行编译 int main() { foo(); // foo()在它的声明/定义之前被调用 } int foo() { p

  • C++快速排序的分析与优化详解

    相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值.具体分析如下: 一.快速排序的介绍 快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n2)[Θ 读作theta].虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择.这是因为其平均情况下的性能相当好:期望的运行时间为 Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小.另外,它还能够进行就地排序,在虚拟内存

  • C++中extern "C"的用法

    学习过C++的人都知道,extern关键字可以置于变量或者函数前,以标示变量或者函数的定义在别的文件中,提示编译器遇到此变量和函数时在其他模块中寻找其定义.这里起到的是声明作用范围的用处.另外,extern还可以与"C"连用,作为链接指示.本文就此进行实例说明如下: 一.C++名字修饰(Name Mangling) 首先需要从C++的重载说起,在C++中函数重载指的是几个函数的函数名相同,参数列表不同.那么当生成obj中间文件/目标文件的时候,C++编译器如何区分这几个重载函数呢?可以

随机推荐