C++实现广度优先搜索实例
本文主要叙述了图的遍历算法中的广度优先搜索(Breadth-First-Search)算法,是非常经典的算法,可供C++程序员参考借鉴之用。具体如下:
首先,图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以
一、广度优先搜索(BFS)的算法思想
广度优先搜索类似于二叉树的层序遍历,它的基本思想就是:首先访问起始顶点v,接着由v出发,依次访问v的各个未访问过的邻接顶点w1,w2,…,wi,然后再依次访问w1,w2,…,wi的所有未被访问过的邻接顶点;再从这些访问过的顶点出发,再访问它们所有未被访问过的邻接顶点……依次类推,直到图中所有顶点都被访问过为止。
广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记录正在访问的顶点的下一层顶点。
如上图所示,为一个有向图,从顶点2开始广度优先遍历整个图,可知结果为2,0,3,1。
二、BFS算法实现
与树相比,图的不同之处在于它存在回路/环,因此在遍历时一个顶点可能被访问多次。为了防止这种情况出现,我们使用一个访问标记数组visited[]来标记顶点是否已经被访问过。
在广度优先搜索一个图之前,我们首先要构造一个图,图的存储方式主要有两种:邻接矩阵、邻接表。这里我们使用邻接表来存储图:
简单起见,我们先假设从起始顶点可以达到其他所有顶点。以有向图为例,C++代码实现:
/************************************************************************* >FileName:BFS.cpp >Author:SongLee ************************************************************************/ #include<iostream> #include<list> usingnamespacestd; /*邻接表存储有向图*/ classGraph { intV;//顶点的数量 list<int>*adj;//邻接表 voidBFSUtil(intv,boolvisited[]); public: Graph(intV);//构造函数 voidaddEdge(intv,intw);//向图中添加一条边 voidBFS(intv);//BFS遍历 }; /*****构造函数*****/ Graph::Graph(intV) { this->V=V; adj=newlist<int>[V];//初始化V条链表 } /*添加边,构造邻接表*/ voidGraph::addEdge(intv,intw) { adj[v].push_back(w);//将w加到v的list } /*从顶点v出发广度优先搜索*/ voidGraph::BFSUtil(intv,boolvisited[]) { //BFS辅助队列 list<int>queue; //将当前顶点标记为已访问并压入队列 visited[v]=true; queue.push_back(v); list<int>::iteratori; 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); } } } } /**广度优先搜索**/ voidGraph::BFS(intv) { //初始化访问标记数组 bool*visited=newbool[V]; for(inti=0;i<V;++i) visited[i]=false; //假设从给定顶点可以到达图的所有顶点 BFSUtil(v,visited); } /*测试*/ intmain() { //创建图 Graphg(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<<"FollowingisBFSTraversal(startingfromvertex2)\n"; g.BFS(2); cout<<endl; return0; }
上面是假设从起始顶点开始能够访问到图的所有顶点。如果不能到达所有顶点,即存在多个连通分量呢?那么我们就要对每个连通分量都进行一次广度优先搜索。
伪代码如下:
boolvisited[MAX_VERTEXT_NUM];//访问标记数组 voidBFS(GraphG)//设访问函数为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 } voidBFSUtil(GraphG,intv) { 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()函数部分:
voidGraph::BFS() { //初始化访问标记数组 bool*visited=newbool[V]; for(inti=0;i<V;++i) visited[i]=false; //对每个连通分量调用一次BFSUtil(),从0号顶点开始遍历 for(inti=0;i<V;++i) if(!visited[i]) BFSUtil(i,visited); }
对于无向图的广度优先搜索,只是邻接表不一样,其他的都是一样的。我们只需要修改addEdge(v,w)函数:
voidGraph::addEdge(intv,intw) { 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)。
注:
相关文章
- EasyC++64,运算符重载
- C/C++ 杂项
- C++继承的基本语法与三种继承方式
- 常胜将军问题(C++版)
- 【c++】【基础】【primer_plus】【第十章】面向对象与类
- Visual Studio 配置 Halcon C++ 运行环境
- C/C++ 实现ShellCode编写与提取
- C++ 使用Socket实现主机间的UDP/TCP通信
- C++虚析构函数详解
- C++ partition_copy(STL partition_copy)算法使用详解
- C++重载插入运算符(<<)和提取运算符(>>)详解
- C++随机数(rand和srand)函数用法详解
- 编写一个简单的游戏来练习用 C++ 编程
- c++读取sqlserver示例分享
- 《C++primerplus》读书笔记(一)
- C++封装远程注入类CreateRemoteThreadEx实例
- C++之WSAAsyncSelect模型实例
- C++基础入门教程(九):函数指针之回调
- C++指向函数的指针实例解析
- C++实现判断字符串是否回文实例解析
- VC++操作SQLite简单实例
- C++继承中的访问控制实例分析