基本图算法(一) 图的广度优先搜索和深度优先搜索

一、广度优先搜索

1.1 广度优先搜索的基本思想与执行过程

广度优先搜索是一个逐层遍历的过程。在每步中，首先访问当前顶点$u$，设置该顶点的访问标志visited[u]=True。接着依次访问结点$u$的所有未访问过的邻接节点$v_1,v_2,\cdots ,v_t\in Adj[u]$，然后再顺序访问$v_1,v_2,\cdots ,v_t\in Adj[u]$的所有未访问过的邻接节点，直到图中的所有节点都被访问过为止。广度优先搜索不是一个递归和回溯的过程，为了实现逐层访问，算法中使用一个队列来存储正在访问的一层和上一层的节点(这也决定了第二节中BFS的特殊性质)，便于访问下一层节点。

给定图$G=(V,E)$和一个源节点$s$，广度优先搜索对图$G$中的边进行探索发现可以从源节点$s$到达的所有节点。为了方便后面的讨论，研究广度优先搜索的性质，我们在概念上将每个节点涂上白色、灰色和黑色，以表示某个节点当前的状态。

$\cdot$「未发现」：我们还没有访问过这个节点，标记为白色，visited[v]=False；

$\cdot$「已发现」：我们已经访问过这个节点，为了更准确的区分，我们将这样的节点分为两类：若是与该节点相连的所有节点都处于「已发现」的状态，那么将该节点标记为黑色，否则标记为灰色，visited[v]=True。

下面是BFS的伪代码：

我们结合下图理解BFS在给定图$G$和源节点$s$上的执行过程：
首先将除了源节点$s$外的所有节点都标记为「未发现」状态，然后将源节点$s$标记为灰色，然后将其入队Q。之后，每次从队列中取出队首节点$u$，考察它的所有邻节点Adj[$u$]，若某个节点$v\in Adj[u]$的状态为未发现，即$v.color==WHITE$，那么就可以访问节点$v$，将其标记为$v.color=GRAY$，然后将$v$入队。一直重复以上过程，直到队列为空，那么入队节点序列就是对图$G$在源节点$s$上执行BFS的遍历序列。

1.2 广度优先搜索的正确性与性质

在证明BFS的正确性和性质前，我们先分析该算法的复杂度。我们采用聚合分析，在初始化后，BFS不会给任何节点涂上白色，那么算法13行的条件就保证了每个节点最多入队一次、出队一次，单次入队和出队的时间为$O(1)$，因此对整个队列操作的时间消耗为$O(V)$。因为算法只有在某个节点入队时才会对邻接表进行扫描，因此用于扫描整个邻接表的时间为$O(E)$。1-8行初始化的消耗为$O(V)$，因此BFS在图$G(V,E)$上的运行时间为$O(V+E)$。算法需要一个大小为$O(V)$的队列，因此空间复杂度为$O(V)$。

在执行广度优先搜索的过程中会构造出一棵广度优先树。一开始，该树只有一个根节点，即源节点$s$。在扫描已发现节点$u$的邻接链表时，每发现一个白色节点$v$，就将该节点$v$和边$(u,v)$加入该棵树中，我们称节点$u$是节点$v$的前驱节点。由于BFS的过程中，每个节点只会被发现一次，因此每个节点最多只有一个前驱节点。如果节点$u$是从根节点$s$到节点$v$的简单路径上的一个节点，则称节点$u$是节点$v$的祖先，节点$v$是节点$u$的后代。为表示各个节点之间的访问先后关系，我们用$\pi$属性来维护各个节点的前驱后继关系，若节点$u$是节点$v$的前驱节点，则记为$v.\pi =u$，如果一个节点没有前驱节点，则认为它的$\pi$属性为NIL。

广度优先搜索之所以得名是因为它将已发现节点和未发现节点之间的边界，沿其广度方向扩展，也就是说，算法需要在发现所有距源节点$s$为$k$的节点之后，才会发现距离为$k+1$的节点。为了更好地研究访问顺序的关系，我们用$d$属性来记录某个节点$u$在执行BFS时到源节点的距离$u.d$。

我们在最初的的代码上做出适当修改，来维护$\pi$和$d$这两个新的属性，在初始化时，将除源节点$s$外的所有节点的$d$置为$\infty$，$\pi$置为NIL，将源节点$s$的$d$置为0，$\pi$置为NIL。

那么，BFS结束时，图$G$的状态应该如下图：

最短路径

接下来我们讨论广度优先搜索的最短路径性质，这里的最短路径不同于带权图的概念，我们定义从源节点$s$到节点$v$的最短路径距离$\delta (s,v)$为节点$s$到节点$v$的所有路径里最小的边数。特别地，若是从节点$s$到节点$v$之间没有路径，那么$\delta (s,v)=\infty$。我们称从节点$s$到节点$v$的长度为$\delta (s,v)$的路径为$s$到$v$的最短路径，而广度优先搜索可以计算出从以源节点$s$到每个节点的最短路径。

我们先证明一个最短路径的性质：

给定一个有向图或无向图$G=(V,E)$，设$s\in V$为任意节点，对于任意边$(u,v)\in E$，有$\delta (s,v)\le \delta (s,u)+1$。

如果节点$u$是从源节点$s$可到达的节点，那么$v$也是从源节点$s$可到达的。在这种情况下，从源节点到节点$v$的最短路径不可能比从源节点到节点$u$的最短路径加上边$(u,v)$更长，因此上述不等式成立。若是节点$u$不能从源节点$s$到达，即$\delta (s,v)=\infty$，那么不等式仍然成立。

接下来只要可以证明，在BFS结束时，对于节点$v\in V$，都有$v.d=\delta (s,v)$，即证明$v.d\ge \delta (s,v)$且$v.d\le \delta (s,v)$。

首先证明上界:$v.d\ge \delta (s,v)$。我们归纳假设：对于所有的节点$v\in V$，$v.d\ge \delta (s,v)$。
归纳的基础是考虑算法第9行源节点$s$加入队列后的情况，此时$s.d=0=\delta (s,s)$，并且对于所有的节点 v ∈ V − { s } v \in V-\left \{ s\right \} v∈V−{s}，$v.d=\infty >\delta (s,v)$。对于归纳步，考虑对$u$的邻接表搜索发现白色节点$v$，根据归纳假设，有$u.d\ge \delta (s,u)$。而算法第15行的赋值操作保证了$v.d=u.d+1\ge \delta (s,u)+1\ge \delta (s,v)$，之后节点$v$被标记为灰色放入队列中，$v.d$不会发生变化，因此归纳假设成立。

接下来证明下界：$v.d\le \delta (s,v)$。为了证明这个不等式，我们先观察算法的执行过程，可以得到如下几个BFS的特点：

在BFS执行的任何时刻，队列$Q$中最多包含两个不同的$d$值，并且对于队列中的两个节点$v_i$和$v_j$，若$v_i$先于$v_j$入队，那么$v_i.d\le v_j.d$。

上述性质表明，在节点加入队列的过程中，$d$的值随时间单调递增。于是，我们可以根据这些特点来证明BFS的正确性。如下：

(广度优先搜索的正确性) 设$G=(V,E)$为一个有向图或无向图，BFS在源节点$s$上运行。那么在算法执行的过程中，BFS将发现从源节点$s$可以到达的所有节点$v$，并且在算法终止时，对所有的节点$v\in V$，都有$v.d=\delta (s,v)$。而且，对于任意可从$s$到达的节点$v\ne s$，从源节点$s$到节点$v$的其中一条最短路径为从节点$s$到节点$v.\pi$的最短路径加上边$(v.\pi ,v)$。

我们采用反证法：假设某些节点获取的$d$值不等于其最短路径长度，设$v$为这样一个节点，其最短路径距离为$\delta (s,v)\ne v.d$。根据之前提到的BFS的性质，$v.d\ge \delta (s,v)$，因此有$v.d>\delta (s,v)$。并且，节点$v$必然是可以从$s$到达的，否则将出现$\delta (s,v)=\infty \ge v.d$。设$u$为从源节点$s$到节点$v$的最短路径上的节点$v$的前驱节点，则$\delta (s,v)=\delta (s,u)+1$，由于$\delta (s,u)=u.d$，因此有：$$v.d>\delta (s,v)=\delta (s,u)+1=u.d+1\cdots (1)$$
现在我们考虑算法第11行的出队操作。当节点$u$从队列中取出，考虑节点$v\in Adj[u]$，节点$v$可能为三种颜色：如果$v$为白色，那么那么在算法的第15将进行赋值：$v.d=u.d+1$，这与(1)式相矛盾；如果$v$为灰色，那么节点$v$是在某个节点$w$出队时做为其未发现的邻节点而被设置成灰色的，节点$w$在节点$u$之前出队，那么$w.d\le u.d$并且$v.d=w.d+1$，因此有$v.d\le u.d+1$，这与(1)式相矛盾；如果节点$v$为黑色，该节点已经在算法的第11行从队列中删除，因此$v.d\le u.d$，这与(1)式相矛盾。综上所述，对于所有的节点$v\in V$，$v.d=\delta (s,v)$。
接下来，由于算法的第16行，如果$v.\pi =u$，那么必然有$v.d=u.d+1$。因此，根据$v.d=\delta (s,v)$，我们可以通过将从源节点$s$到节点$v.\pi$的最短路径加上边$(v.\pi ,v)$，即可获得从源节点到节点$v$的最短路径。至此，BFS最短路径的性质和正确性得证!

广度优先树

接下里我们研究BFS作用在图$G=(V,E)$的源节点$s$上产生广度优先树的性质。正如代码执行流程图中显示的，我们在每次确定$v.\pi =u$这个前驱后继关系时将边$(u,v)$进行标记，就可以得到一棵广度优先树，这棵树代表了图$G$的$\pi$属性。

对于图$G=(V,E)$和源节点$s$，我们定义图$G$的前驱子图为$G_{\pi }=(V_{\pi },E_{\pi })$，其中 V π = { v ∈ V : v . π ≠ N I L } ∪ { s } V_{\pi}=\left \{ v\in V:v.\pi\neq NIL \right \}\cup\left \{ s \right \} Vπ​={v∈V:v.π=NIL}∪{s}， E π = { ( v . π , v ) : v ∈ V π − { s } } E_{\pi}=\left \{ (v.\pi,v):v\in V_{\pi}-\left\{ s\right\} \right \} Eπ​={(v.π,v):v∈Vπ​−{s}}。如果$V_{\pi }$由从源节点$s$可以到达的节点组成，并且对于所有的$v\in V_{\pi }$，子图$G$包含一条从源节点$s$到节点$v$的唯一简单路径(路径中的顶点互不相同)，且该路径也是图$G$里面从源节点$s$到节点$v$之间的一条最短路径，那么前驱子图$G_{\pi }$就是一棵广度优先树，$E_{\pi }$就是广度优先树的树边，并且满足$E_{\pi }=V_{\pi }-1$。下图就是BFS作用在图$G$和源节点$s$产生的一棵广度优先树。

接下来我们证明：BFS过程生成的前驱子图$G_{\pi }$是一棵广度优先树。即当运行在一个有向或无向图$G(V,E)$上，BFS过程所建造出来的$\pi$属性使得前驱子图$G_{\pi }=(V_{\pi },E_{\pi })$成为一棵广度优先树。
在算法第16行设置$v.\pi =u$当且仅当$(u,v)\in E$且$\delta (s,v)<\infty$，即如果节点$v$可以从源节点$s$到达，$V_{\pi }$由从源节点$s$可以到达的$V$集合里的顶点组成。由于$G_{\pi }$形成一棵树，该树包含从源节点$s$到$V_{\pi }$中每个节点的的一条唯一简单路径。根据“广度优先搜索的正确性”，每条这样的路径也是图$G$中的一条图$G$里面的一条最短路径。

1.3 广度优先搜索的代码实现

这里假设图$G$通过邻接表的方式存储，顶点表和边表的定义如下：

typedef struct _EdgeNode {
	int adjvex;    //该边的终点在顶点表中的下标
	struct _EdgeNode* next;
}EdgeNode;    // 边表 

typedef struct _VertexNode {
	bool visited;
	int d;
	struct _EdgeNode* firstEdge;  //指向第一条边所对应的边节点
}VertexNode;  // 顶点表

typedef struct AdjancencyListGraph {
	VertexNode* vertices;
	int vertexNum, edgeNum;
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

下面是BFS作用在图$G=(V,E)$和源节点$s$上的代码。

void bfsALGraph(ALGraph G, int s)
{
	for (int i = 0; i < G.V; i++){
		G.vertices[i].visited = false;
		G.vertices[i].d = INT_MAX;
	}
	Queue q;
	Visit(G.vertices[s]);
	G.vertices[s].visited = true;
	G.vertices[s].d = 0;
	QueuePush(&q, s);
	while (!QueueEmpty(&q))
	{
		int u = QueuePop(&q);
		EdgeNode* cur = G.vertices[u].firstEdge;
		// 处理所有邻接节点v
		while (cur)
		{
			if (!G.vertices[cur->adjvex].visited)
			{
				Visit(G.vertices[cur->adjvex]);
				G.vertices[cur->adjvex].visited = true;
				G.vertices[cur->adjvex].d = G.vertices[u].d + 1;
				QueuePush(&q, cur->adjvex);
			}
			cur = cur->next;
		}
	}
}
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

二、深度优先搜索

2.1 深度优先搜索的基本思想与执行过程

正如名字所隐含的，深度优先搜索的策略是只要可能，就在图中尽量深入。深度优先搜索总是对最近发现的节点$v$的出发边进行探索，直到改节点的所有出发边都被探索过为止。一旦节点$v$的所有出发边都被探索，搜索则回溯到$v$的前驱节点$u$($v$是经过节点$u$被发现的)，来搜索改前驱节点的出发边。

也就是说，在每一步的探查中，首先对当前节点v进行访问，然后对节点v设置访问标志visited[v] = true。接着在v的所有邻接节点中寻找尚未访问的一个，将其作为下一步探查的节点。倘若当前节点的所有临界节点都被访问过，则回退一步，将前一步被访问的节点重新取出，当作探查的当前节点。重复上述过程，直到所有节点都被访问到，此时连通图的所有节点便被全部访问。

为了方便后面的讨论，研究深度优先搜索的性质，我们在概念上将每个节点涂上白色、灰色和黑色，以表示某个节点当前的状态。

$\cdot$「未发现」：我们还没有访问过这个节点，标记为白色，visited[v]=False；

$\cdot$「已发现」：我们已经访问过这个节点，为了更准确的区分，我们将这样的节点分为两类：若是与该节点相邻接的所有节点都处于「已发现」的状态，那么将该节点标记为黑色，否则标记为灰色，visited[v]=True。

下面是深度优先搜索的伪代码：

我们结合下图理解DFS在图$G=(V,E)$上的执行过程：DFS(G)的第1、2行将所有节点都设置为未访问状态，第3-5行对图$G$中的每个节点进行检查，当发现未访问的节点时，就对它执行DFS-VISIT。每次执行DFS-VISIT(G,u)，节点$u$的初始状态都是白色，算法的第1行将节点$u$涂上灰色，第2-4行对每个邻接节点$v$进行检查，并在节点$v$状态为白色时递归访问该节点，即探索边$(u,v)$。最后，在每个邻接节点都被检查后，将节点$v$涂上黑色。

2.2 深度优先搜索的正确性与性质

在分析深度优先搜索的正确性和性质前，我们先研究该算法的复杂度。如果排除DFS-VISIT的时间，DFS算法的第1-2行和3-5行循环需要的时间为$\Theta (V)$，接着我们用聚合分析来研究所有DFS-VISIT操作共花费的时间。对于每个节点$v\in V$，DFS-VISIT恰好被调用一次，这是因为一个节点只有在它处于未访问状态才可以执行DFS-VISIT，而DFS-VISIT又会将该节点涂上灰色和黑色。对于DFS-VISIT过程，2-4行的循环执行次数为$|Adj[v]|$，则所有DFS-VISIT操作的总花费为${\sum }_{v\in V}|Adj[v]|=\Theta (E)$，因此，DFS(G,s)的时间复杂度为$O(V+E)$。而DFS的空间消耗主要在于递归过程中的栈开销，递归深度最大为$O(V)$，其他额外空间为常数级消耗，因此DFS的空间复杂度为$O(V)$。

像广度优先搜索一样，在对已发现的节点$u$的邻接链表进行扫描时，每当发现一个未访问的白色节点$v$，深度优先搜索对其进行记录，也是采用$\pi$属性来表示前驱关系，将$v$的前驱属性$v.\pi$设置为$u$。不过，与广度优先搜索不同的是，深度优先搜索形成的前驱子图不一定是一棵树，而有可能是多棵树，这是因为深度优先搜索可能从多个节点出发重复进行。因此，我们这样定义深度优先搜索形成的前驱子图：设图$G_{\pi }=(V,E_{\pi })$，其中， E π = { ( v . π , v ) : v ∈ V & v . π ≠ N I L } E_{\pi}=\left \{ (v.\pi,v):v\in V\&v.\pi \neq NIL \right \} Eπ​={(v.π,v):v∈V&v.π=NIL}。深度优先搜索的前驱子图形成一个由多棵深度优先树构成的深度优先森林，其中森林$E_{\pi }$中的边成为树边。

为了更好地研究深度优先搜索形成的深度优先森林的性质，我们在每个节点上设置两个时间戳：第一个时间戳$v.d$记录节点$v$第一次被发现的时间(涂上灰色的时候)，第二个时间戳$v.f$记录完成对节点$v$的邻接链表扫描的时间(涂上黑色的时候)。这些时间戳和前驱属性$\pi$可以为我们提供深度优先森林的重要信息，我们在2.1节的代码上做出适当修改，以维护每个节点的$\pi$属性和时间戳。

那么，DFS结束时，图$G$状态应该如下图所示：

随着算法在有向图上对边探索的推进，这些边变成蓝色的边(树边)或者是带虚线的边(非树边)。非树边可以分为三类：后向边、前向边和横向边。图中的每个节点都被标记上时间戳以表示该节点的发现时间和搜索完成时间。

括号化定理

接下来我们就可以证明深度优先搜索的性质。深度优先搜索的一个重要性质是，节点的发现时间$v.d$和完成时间$v.f$具有括号化结构。如果以左括号"(u"表示节点$u$的发现，右括号"u)"表示节点$u$的完成，则所有节点的括号将适当地嵌套在一起。

于是我们有括号化定理：

在对无向或无向图$G=(V,E)$进行的任意深度优先搜索中，对于任意两个节点$u$和$v$来说，下面三种情况只有一种成立：
$\cdot$ 区间$[u.d,u.f]$和区间$[v.d,v.f]$完全分离，在深度优先森林中，节点$u$不是$v$的后代或前驱。
$\cdot$ 区间$[u.d,u.f]$完全包含在区间$[v.d,v.f]$中，在深度优先森林中，节点$u$是节点$v$的后代。
$\cdot$ 区间$[v.d,v.f]$完全包含在区间$[u.d,u.f]$中，在深度优先森林中，节点$v$是节点$u$的后代。

深度优先搜索的括号化定理是许多依赖于深度优先搜索的算法的基础，如拓扑排序，只要将深度优先搜索的结果按照各个节点的完成时间$v.f$逆序排序，就可以得到一个有向无环图$G$的拓扑序列，这就是运用了括号化定理根据$v.d$和$v.f$判断节点的前驱后继关系。

边的分类

我们通过深度优先搜索对图$G=(V,E)$的边进行分类，定义4种边类型：

$\cdot$ 树边(Tree Edge)：深度优先树森林$G_{\pi }$中的边。如果节点$v$是因算法对边$(u,v)$进行探索而首先被发现的边，则$(u,v)$是一条树边。
$\cdot$ 后向边(Back Edge)：后向边$(u,v)$是将节点$u$连接在其深度优先树中的一个祖先节点$v$的边。特别的，自循环也可认为是后向边。
$\cdot$ 前向边(Forward Edge)：前向边$(u,v)$是将节点$u$连接到其在深度优先树中一个后代节点$v$的边。
$\cdot$ 横向边(Cross Edge)：指其他所有的边，这些边可以连接不同深度优先树的两个节点，也可以连接同一棵深度优先树中的节点，只要其中一个节点不是另外一个节点的祖先。

在DFS第一次探索边$(u,v)$时，可以根据节点$v$的边来判断边的类型：

1. 当节点$v$为白色，该边为一条树边。
2. 当节点$v$为灰色，该边为一条后向边。
3. 当节点$v$为黑色，该边为一条前向边或横向边。

通过节点$u$和节点$v$的时间戳，我们也可以判断边$(u,v)$的类型：

1. $(u,v)$是树边或前向边当且仅当$u.d<v.d<v.f<u.f$。
2. $(u,v)$是后向边当且仅当$v.d\le u.d<u.f\le v.f$。
3. $(u,v)$是横向边当且仅当$v.d<v.f<u.d<u.f$ 。

对第一种判定方式的证明过程如下：
第一种情况是由DFS算法的5-6行所确定的。

第二种情况，灰色节点可以构成一条对应于当前活跃的DFS-VISIT调用栈的后代链，灰色节点数量总是比深度优先森林中最近被发现都节点数多1，而DFS-VISIT的思想就是从深度最深的灰色节点往前一直推进，因此当从灰色节点通向另一个灰色节点所到达的总是当前灰色节点的祖先。

第三种情况，我们结合第二种判定方式进行讨论，如果$(u,v)$是一条横向边，那么节点$u$和$v$互相都不是对方祖先或后代，根据括号化定理的第一条，区间$[u.d,u.f]$和区间$[v.d,v.f]$应该完全分离，因此，只有两种可能：$v.d<v.f<u.d<u.f$或是$u.d<u.f<v.d<v.f$，我们假设$u.d<v.d$，那么当节点$u$被发现并且涂上灰色时，节点$v$为白色未被发现，那么由于边$(u,v)$的存在，节点$v$会成为节点$u$的后代，这与横向边的定义矛盾，故当$(u,v)$为横向边，有$v.d<v.f<u.d<u.f$ ；另一方面，若是有$v.d<v.f<u.d<u.f$，根据括号化定理的第一条，节点$u$和节点$v$互相不为祖先或者后代的关系，即$(u,v)$是一条横向边。如果$(u,v)$是一条前向边，那么节点$u$是节点$v$的祖先，根据括号化定理的第三条，有区间$[v.d,v.f]$完全包含在区间$[u.d,u.f]$中，即$u.d<v.d<v.f<u.f$；另一方面，若是有$u.d<v.d<v.f<u.f$，那么根据括号化定理的第三条，可知节点$u$是节点$v$的祖先，于是边$(u,v)$只能是树边或前向边，由于边$(u,v)$不是树边，因此边$(u,v)$是前向边。

2.3 深度优先搜索的代码实现

这里假设图$G$通过邻接表的方式存储，顶点表和边表的定义如下：

typedef struct _EdgeNode {
	int adjvex;    //该边的终点在顶点表中的下标
	struct _EdgeNode* next;
}EdgeNode;    // 边表 

typedef struct _VertexNode {
	bool visited;
	int prev;                     //记录当前节点的前驱
	struct _EdgeNode* firstEdge;  //指向第一条边所对应的边节点
}VertexNode;  // 顶点表

typedef struct AdjancencyListGraph {
	VertexNode* vertices;
	int vertexNum, edgeNum;
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

下面是DFS作用在图$G=(V,E)$的代码：

void DFS_Visit(ALGraph G, int v) {
	Visit(G.vertices[v].vertex);
	visited[v] = true;
	EdgeNode* cur = G.vertices[v].firstEdge; // cur->adjvex 是 与节点v相连节点的下标
	while (cur)
	{
		if (!G[cur->adjvex].visited) {
			G[cur->adjvex].prev = v;
			DFS_Visit(G, cur->adjvex, visited);
		}
		cur = cur->next;
	}
}

void DFS(ALGraph G, int v) {
	for (int i = 0; i < G.vertexNum; i++) {
		G.vertices[i].visited = false;
		G.vertices[i].prev = -1;
	}
	for (int i = 0; i < G.vertexNum; i++) {
		if (!G.vertices[i].visited) 
			DFS_Visit(G, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三、BFS和DFS的应用

3.1 树的直径

我们将一棵树$T=(V,E)$的直径定义为$\underset{u,v\in V}{\max }\delta (u,v)$，也就是说，树中所有最短路径距离的最大值即为树的直径。

方法一：我们任意选取一个源节点$s$，对其执行BFS，记录下最后一个被访问的节点$u$，然后以$u$为源节点，对其执行BFS，记录下最后一个被访问的节点$v$，那么$\delta (u,v)$就是树的直径。

方法二：我们任意选取一个源节点$s$，对其执行DFS，找到距离源节点最远的点$u$，然后以$u$为源节点，对其执行DFS，记录下距离$u$最远的节点$v$，那么$\delta (u,v)$就是树的直径。

以上方法的成立依赖于以下定理：

在一棵树上，从任意节点$y$开始进行一次 DFS/BFS，到达的距离其最远的节点$z$必为直径的一端。

通过反证法简单证明如下：记树$T=(V,E)$的真实直径为$\delta (u,v)$，那么$u$和$v$是直径的两个端点，我们假设从节点$y$出发做一次DFS或者BFS找到的距离$y$最远的节点$z$不是$u$或$v$。

代码如下：

3.2 强连通分量