C++实现广度优先搜索实例(2)
根据伪代码，相信不难写出对于多个连通分量的图的广度优先搜索。我们只需要修改BFS()函数部分： void Graph::BFS() { // 初始化访问标记数组 bool *visited = n
根据伪代码，相信不难写出对于多个连通分量的图的广度优先搜索。我们只需要修改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最小生成树算法。
- 上一篇：C++深度优先搜索的实现方法
- 下一篇：C++实现第K顺序统计量的求解方法
收藏文章
精彩图集
精彩文章
