基本图算法（广度优先搜索和深度优先搜索）

痛定思痛。 2022-08-25 02:20 222阅读 0赞

图算法对于计算机学科至关重要。成百上千的计算问题最后都可以归约为图论问题。本文主要是对《算法导论》图算法的学习笔记进行整理。

首先，我们先对图算法中的一些表达方式进行统一：给定图G=(V,E)，当对该图上的一个算法的运行时间进行表述时，我们通常以图的结点数|V|和边的条数|E|作为输入的规模。另外，我们用G.V来表示图G的结点集，用G.E表示图G的边集合，也就是说，我们将结点和边看作是图的属性。

**图的表示**

对于图G=(V,E)，可以用两种标准表示方法表示。一种表示法是将图作为邻接链表的组合，另一种是将图作为邻接矩阵来看待。

**邻接链表**

邻接链表表示由一个包含|V|条链表的数组Adj所构成，每个结点有一条链表。对于每个结点u，邻接链表Adj\[u\]包含所有与结点u之间有边相连的结点v。邻接链表在表示稀疏图上很有优势。邻接链表的一个潜在缺陷是无法快速判断一条边(u,v)是否是图中的一条边，唯一的方法是在邻接链表Adj\[u\]里面搜索结点v。邻接矩阵克服了这个缺陷，但付出的代价是更大的存储空间消耗。

**邻接矩阵**

对邻接矩阵表示来说，我们通常会将图G中的结点编为1、2、……、|V|，这种编号可以任意。在进行编号之后，图G的邻接矩阵表示一个|V|\*|V|的矩阵A=(aij)予以表示，该矩阵满足下述条件：

aij=1 if (i,j)属于E；否则 aij=0.

关于图的两种表示的一个例子如下所示，其中（b）为链表，（c）为矩阵表示。

![SouthEast][]

**广度优先搜索**

广度优先搜索是最简单的图搜索算法之一，也是许多重要的图算法的原型。Prim的最小生成树算法和Dijkstra的单源最短路径算法都使用了类似广度优先搜索的思想。

**概述**：

给定图G=(V,E)和一个可识别的源结点s，广度优先搜索对图G中的边进行系统性的探索来发现可以从源结点s到达的所有结点。该算法能够计算从源结点s到每个可到达结点的距离（最少的边数），同时生成一棵“广度优先搜索树”。该树以源结点s为根结点，包含所有可从s到达的结点。

该算法始终是将已发现结点和未发现结点之间的边界，沿其广度方向扩展，也即是说，算法需要在发现所有距离源结点s为k的所有结点之后，才会发现距离源结点s为k+1的其他结点。

在广度优先搜索过程BFS中，假定G的邻接链表表示，u.color为颜色属性，u.front存放u的前驱结点，u.d记录的是广度优先搜索算法所计算出的从s到达u之间的距离。

**伪代码**如下：

BFS(G,s)
    	for each vertex u ∈ G.V-{s}
    		u.color = WHITE
    		u.d = inf
    		u.front = NIL
    	s.color = Gray
    	s.d = 0
    	s.front = NIL
    	Q = 空集
    	ENQUEUE(Q,s)
    	while Q != 空集
    		u = DEQUEUE(Q)
    		for each v ∈ G.Adj[u]
    			if v.color == WHITE
    				v.color = Gray
    				v.d = u.d +1
    				v.front = u
    				ENQUEUE(Q,v)
    		u.color = BLACK

**深度优先搜索**

深度优先搜索总是对最近才发现的结点v的出发边进行探索，知道该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，搜索则回溯到v的前驱结点，来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有的结点都被发现为止。若尚存在未发现结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。

与广度优先搜索不同的是，广度优先搜索的前驱子图形成一棵树，而深度优先搜索的前驱子图可能由多棵树组成，因为搜索可能从多个源结点重复进行。这些前驱子图形成深度优先森林。

深度优先算法在每个结点盖上一个时间戳。每个结点v有两个时间戳，第一个时间戳v.d记录结点v第一次被发现的时间，第二个v.f记录的是搜索完成对v的邻接链表扫描的时间。

**伪代码**如下：

DFS(G)
    	for each vertex u∈ G.V
    		u.color = WHITE
    		u.front = NIL
    	time = 0
    	for each vertex u∈ G.V
    		if u.color == WHITE
    			DFS-VISIT(G,u)
    
    DFS-VISIT(G,u)
    	time = time+1
    	u.d = time
    	u.color = Gray
    	for each vertex v∈G:Adj[u]
    		if v.color == WHITE
    			v.front = u
    			DFS-VISIT(G,V)
    	u.color = BLACK
    	time = time+1
    	u.f = time

[SouthEast]: /images/20220824/b87206204a08480ca2f55c4b6726e9ca.png