广度优先搜索的实现

发表于   |   分类于   |  

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

广度优先搜索（BFS）的算法思想

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

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

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

BFS算法实现

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*************************************************************************
    > File Name: BFS.cpp
    > Author: SongLee
    > E-mail: lisong.shine@qq.com
    > Created Time: 2014年07月03日 星期四 18时37分59秒
    > Personal Blog: songlee24.github.io
 ************************************************************************/
#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;
}

上面是假设从起始顶点开始能够到达图的所有顶点。如果不能到达所有顶点，即存在多个连通分量呢？那么我们就要对每个连通分量都进行一次广度优先搜索。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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()函数部分：

1
2
3
4
5
6
7
8
9
10
11
12
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)函数：

1
2
3
4
5
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最小生成树算法。