第九章 图的遍历算法
- 格式：ppt
- 大小：198.00 KB
- 文档页数：49
下载文档原格式
合集下载
图的遍历算法
1图的遍历问题在实践中常常遇到这样的问题：给定n个点，从任一点出发对所有的点访问一次并且只访问一次。
如果用图中的顶点表示这些点，图中的边表示可能的连接，那么这个问题就可以表示成图的遍历问题，即从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
图的遍历操作和树的遍历操作功能相似，是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础上。
由于图结构本身的复杂性，所以图的遍历操作也比较复杂，主要表现在以下几个方面：(1) 在图结构中，没有一个确定的首结点，图中任意一个顶点都可以作为第一个被访问的结点。
(2) 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需要考虑如何选取下一个出发点以访问图中其余的连通分量。
(3) 在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点。
⑷在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
基于以上分析，图的遍历方法目前有深度优先搜索(DFS)和广度优先搜索(BFS)两种算法。
下面将介绍两种算法的实现思路，分析算法效率并编程实现。
1.1深度优先搜索算法深度优先搜索算法是树的先根遍历的推广，它的实现思想是：从图G的某个顶点V o出发，访问V o,然后选择一个与V o相邻且没被访问过的顶点V i访问，再从V i出发选择一个与V i相邻且未被访问的顶点V j进行访问，依次继续。
如果当前被访问过的顶点的所有邻接顶点都已被访问，贝U退回已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样的方法向前遍历，直到图中所有顶点都被访问。
其递归算法如下：Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G Status(*Visit)(i nt v)){VisitF unc = Visit;for(v=0; vvG.vex num; ++v)visited[v] = FALSE; //访问标志数组初始化for(v=0; v<G .vex num; ++v)if(!visited[v])DFS(G v); //对尚未访问的顶点调用DFS}void DFS(Graph G int v){ //从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE; VisitFunc(v); // 访问第v 个顶点for(w=FirstAdjVex(G ,v); w>=0;w=NextAdjVex(G ,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)。
第9章 NP完全理论
★定义5 令 是一个判定问题，如果：
（1） NP，即问题属于NP类问题
（2）对NP中的所有问题 ‘，都有 '∝p则称
判定问题是一个NP完全问题，简记为NPC。
典型的NP完全问题
Cook在他1971年的论文中指出：所谓的合取范式可满足性
问题就是NP完全问题 。 几个典型的NP完全问题。 （1）图着色问题COLORING （2）路径问题LONG-PATH （3）顶点覆盖问题VERTEX-COVER （4）子集和问题SUBSET-SUM （5）哈密尔顿回路问题HAM-CYCLE （6）旅行商问题TSP （7）装箱问题BIN-PACKING
学习NP完全理论的意义
今天，NP-complete一词已经成为算法设计者在求解规模大而又
复杂困难的问题时所面临的某种难以逾越的深渊的象征。 2000年初，美国克雷数学研究所的科学顾问委员会选定了七个 “千年大奖问题”，该研究所的董事会决定建立七百万美元的大 奖基金，每个“千年大奖问题”的解决都可获得百万美元的奖励。 克雷数学研究所“千年大奖问题”的选定，其目的不是为了形成 新世纪数学发展的新方向，而是集中在数学家们梦寐以求而期待 解决的重大难题上。NP完全问题排在百万美元大奖的首位，足见 它的显赫地位和无穷魅力。 现在，人们已经认识到，在科学和很多工程技术领域里，常常遇 到的许多有重要意义而又没有得到很好解决的难题是NP完全问题。 另外，由于人们的新发现，这类问题的数目不断增加。
顶点覆盖问题的近似算法的性能比为2。
装箱问题
设有n个物品w1, w2, …,wn和若干个体积
均为C的箱子b1, b2, …,bk,…。n个物品 的 体 积 分 别 为 s1, s2, …,sn 且 有 si≤C(1≤i≤n)。要求把所有物品分别装入 箱子且物品不能分割，使得占用箱子数最 少的装箱方案。 算法设计方案：首次适宜法（近似比小于 2）、最适宜法（近似比小于2）、 首次适
数据结构实验报告图的遍历讲解
数据结构实验报告图的遍历讲解一、引言在数据结构实验中，图的遍历是一个重要的主题。
图是由顶点集合和边集合组成的一种数据结构，常用于描述网络、社交关系等复杂关系。
图的遍历是指按照一定的规则，挨次访问图中的所有顶点，以及与之相关联的边的过程。
本文将详细讲解图的遍历算法及其应用。
二、图的遍历算法1. 深度优先搜索（DFS）深度优先搜索是一种常用的图遍历算法，其基本思想是从一个顶点出发，沿着一条路径向来向下访问，直到无法继续为止，然后回溯到前一个顶点，再选择此外一条路径继续访问。
具体步骤如下：（1）选择一个起始顶点v，将其标记为已访问。
（2）从v出发，选择一个未被访问的邻接顶点w，将w标记为已访问，并将w入栈。
（3）如果不存在未被访问的邻接顶点，则出栈一个顶点，继续访问其它未被访问的邻接顶点。
（4）重复步骤（2）和（3），直到栈为空。
2. 广度优先搜索（BFS）广度优先搜索是另一种常用的图遍历算法，其基本思想是从一个顶点出发，挨次访问其所有邻接顶点，然后再挨次访问邻接顶点的邻接顶点，以此类推，直到访问完所有顶点。
具体步骤如下：（1）选择一个起始顶点v，将其标记为已访问，并将v入队。
（2）从队首取出一个顶点w，访问w的所有未被访问的邻接顶点，并将这些顶点标记为已访问，并将它们入队。
（3）重复步骤（2），直到队列为空。
三、图的遍历应用图的遍历算法在实际应用中有广泛的应用，下面介绍两个典型的应用场景。
1. 连通分量连通分量是指图中的一个子图，其中的任意两个顶点都是连通的，即存在一条路径可以从一个顶点到达另一个顶点。
图的遍历算法可以用来求解连通分量的个数及其具体的顶点集合。
具体步骤如下：（1）对图中的每一个顶点进行遍历，如果该顶点未被访问，则从该顶点开始进行深度优先搜索或者广度优先搜索，将访问到的顶点标记为已访问。
（2）重复步骤（1），直到所有顶点都被访问。
2. 最短路径最短路径是指图中两个顶点之间的最短路径，可以用图的遍历算法来求解。
图的遍历 实验报告
图的遍历实验报告一、引言图是一种非线性的数据结构，由一组节点（顶点）和节点之间的连线（边）组成。
图的遍历是指按照某种规则依次访问图中的每个节点，以便获取或处理节点中的信息。
图的遍历在计算机科学领域中有着广泛的应用，例如在社交网络中寻找关系紧密的人员，或者在地图中搜索最短路径等。
本实验旨在通过实际操作，掌握图的遍历算法。
在本实验中，我们将实现两种常见的图的遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS），并比较它们的差异和适用场景。
二、实验目的1. 理解和掌握图的遍历算法的原理与实现；2. 比较深度优先搜索和广度优先搜索的差异；3. 掌握图的遍历算法在实际问题中的应用。
三、实验步骤实验材料1. 计算机；2. 编程环境（例如Python、Java等）；3. 支持图操作的相关库（如NetworkX）。
实验流程1. 初始化图数据结构，创建节点和边；2. 实现深度优先搜索算法；3. 实现广度优先搜索算法；4. 比较两种算法的时间复杂度和空间复杂度；5. 比较两种算法的遍历顺序和适用场景；6. 在一个具体问题中应用图的遍历算法。
四、实验结果1. 深度优先搜索（DFS）深度优先搜索是一种通过探索图的深度来遍历节点的算法。
具体实现时，我们可以使用递归或栈来实现深度优先搜索。
算法的基本思想是从起始节点开始，选择一个相邻节点进行探索，直到达到最深的节点为止，然后返回上一个节点，再继续探索其他未被访问的节点。
2. 广度优先搜索（BFS）广度优先搜索是一种逐层遍历节点的算法。
具体实现时，我们可以使用队列来实现广度优先搜索。
算法的基本思想是从起始节点开始，依次遍历当前节点的所有相邻节点，并将这些相邻节点加入队列中，然后再依次遍历队列中的节点，直到队列为空。
3. 时间复杂度和空间复杂度深度优先搜索和广度优先搜索的时间复杂度和空间复杂度如下表所示：算法时间复杂度空间复杂度深度优先搜索O(V+E) O(V)广度优先搜索O(V+E) O(V)其中，V表示节点的数量，E表示边的数量。
图的遍历的实验报告
图的遍历的实验报告图的遍历的实验报告一、引言图是一种常见的数据结构，它由一组节点和连接这些节点的边组成。
图的遍历是指从图中的某个节点出发，按照一定的规则依次访问图中的所有节点。
图的遍历在许多实际问题中都有广泛的应用，例如社交网络分析、路线规划等。
本实验旨在通过实际操作，深入理解图的遍历算法的原理和应用。
二、实验目的1. 掌握图的遍历算法的基本原理；2. 实现图的深度优先搜索（DFS）和广度优先搜索（BFS）算法；3. 比较并分析DFS和BFS算法的时间复杂度和空间复杂度。
三、实验过程1. 实验环境本实验使用Python编程语言进行实验，使用了networkx库来构建和操作图。
2. 实验步骤（1）首先，我们使用networkx库创建一个包含10个节点的无向图，并添加边以建立节点之间的连接关系。
（2）接下来，我们实现深度优先搜索算法。
深度优先搜索从起始节点开始，依次访问与当前节点相邻的未访问过的节点，直到遍历完所有节点或无法继续访问为止。
（3）然后，我们实现广度优先搜索算法。
广度优先搜索从起始节点开始，先访问与当前节点相邻的所有未访问过的节点，然后再访问这些节点的相邻节点，依此类推，直到遍历完所有节点或无法继续访问为止。
（4）最后，我们比较并分析DFS和BFS算法的时间复杂度和空间复杂度。
四、实验结果经过实验，我们得到了如下结果：（1）DFS算法的时间复杂度为O(V+E)，空间复杂度为O(V)。
（2）BFS算法的时间复杂度为O(V+E)，空间复杂度为O(V)。
其中，V表示图中的节点数，E表示图中的边数。
五、实验分析通过对DFS和BFS算法的实验结果进行分析，我们可以得出以下结论：（1）DFS算法和BFS算法的时间复杂度都是线性的，与图中的节点数和边数呈正比关系。
（2）DFS算法和BFS算法的空间复杂度也都是线性的，与图中的节点数呈正比关系。
但是，DFS算法的空间复杂度比BFS算法小，因为DFS算法只需要保存当前路径上的节点，而BFS算法需要保存所有已访问过的节点。
遍历路径算法
遍历路径算法遍历路径算法是一种计算机科学中的算法，用于在图或树等数据结构中遍历或搜索路径，以找到特定节点、确定连通性或执行其他操作。
以下是一些常见的遍历路径算法：1. 深度优先搜索（Depth-First Search，DFS）：DFS 是一种递归或堆栈（栈）驱动的算法，用于遍历树或图中的节点。
它首先探索一个节点的所有子节点，然后再递归地继续向下探索，直到到达叶子节点，然后返回上一级节点，继续探索其他子节点。
DFS 可以用于寻找路径、检测环、拓扑排序等问题。
2. 广度优先搜索（Breadth-First Search，BFS）：BFS 以层次方式遍历图或树，从根节点开始，首先探索所有直接相邻的节点，然后再逐层向外扩展。
BFS 通常用于寻找最短路径或解决距离相关问题。
3. Dijkstra 算法：Dijkstra 算法用于寻找从一个起点到图中所有其他节点的最短路径。
它通过不断选择距离最短的节点来构建最短路径树。
4. A 搜索算法*：A* 搜索算法是一种启发式搜索算法，用于寻找从一个起点到目标节点的最短路径。
它使用启发式函数来评估节点的价值，并选择具有最小总代价的节点进行探索。
5. 贪婪搜索算法：贪婪搜索算法是一种启发式搜索算法，它总是选择最有希望的节点进行探索，但不一定能够找到全局最优解。
它通常用于解决某些优化问题，如旅行推销员问题。
6. 递归算法：递归算法是一种通过递归调用自身的方法，来遍历树或图中的路径。
递归算法可以用于深度优先搜索和其他遍历任务。
这些算法的选择取决于具体的问题和数据结构。
不同的遍历路径算法适用于不同类型的问题，因此需要根据问题的性质来选择适当的算法。
实现图的遍历算法实验报告
实现图的遍历算法实验报告实现图的遍历算法实验报告⼀实验题⽬: 实现图的遍历算法⼆实验要求:2.1:（1）建⽴如图（p126 8.1）所⽰的有向图 G 的邻接矩阵，并输出之（2）由有向图G的邻接矩阵产⽣邻接表，并输出之（3）再由（2）的邻接表产⽣对应的邻接矩阵，并输出之2.2 （1）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（递归算法）（2）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（⾮递归算法）（3）输出如图8.1所⽰的有向图G从顶点0开始的⼴度优先遍历序列三实验内容:3.1 图的抽象数据类型:ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}VR={|v,w∈V且P(v,w)，表⽰从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
DestroyGraph( &G )初始条件：图G存在。
操作结果：销毁图G。
LocateVex( G, u )初始条件：图G存在，u和G中顶点有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。
GetVex( G, v )初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的值。
PutVex( &G, v, value )初始条件：图G存在，v是G中某个顶点。
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的第⼀个邻接顶点。
若顶点在G中没有邻接顶点，则返回“空”。
NextAdjVex( G, v, w )初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。
操作结果：返回v的（相对于w的）下⼀个邻接顶点。
若w是v 的最后⼀个邻接点，则返回“空”。
InsertVex( &G, v )初始条件：图G存在，v和图中顶点有相同特征。
哈密顿算法遍历
哈密顿算法遍历哈密顿算法是一种常用于图论中的遍历算法，用于寻找图中的哈密顿路径或哈密顿回路。
哈密顿路径是指一个无向图中通过每个顶点一次且仅一次的路径，而哈密顿回路则是指一个无向图中通过每个顶点一次且仅一次的闭合路径。
该算法的实现原理是通过深度优先搜索（DFS）来遍历图中的所有可能路径，在每个顶点上进行回溯，直到找到满足条件的哈密顿路径或回路。
下面将详细介绍哈密顿算法的遍历流程和关键步骤。
1.首先，确定起始顶点。
在哈密顿算法中，起始顶点对结果并不产生影响，因为哈密顿路径或回路可以从任意顶点开始。
因此，选择任意一个顶点作为起点，将其标记为已访问。
2.接下来，进入递归回溯的过程。
从起点开始，选择一个邻接顶点作为下一个访问的节点，并将其标记为已访问。
然后，继续对该邻接顶点进行递归回溯，直到满足下面两个终止条件之一：- 所有的顶点都已经访问过，即构成了一条哈密顿路径或回路。
- 当前深度已经达到图中的总顶点数，但没有形成哈密顿路径或回路。
3.在进行递归回溯时，需要做以下判断：- 判断当前顶点是否为未访问过的顶点，如果是，则选择该顶点作为下一个访问节点，并标记为已访问。
- 判断当前顶点是否与起始顶点相邻，如果是，则判断是否满足哈密顿回路的条件，即所有顶点都已经访问过。
如果是，则输出该路径或回路。
- 判断当前顶点是否与起始顶点不相邻，如果是，则判断是否满足哈密顿路径的条件，即所有顶点都已经访问过。
如果是，则输出该路径。
4.若当前顶点的邻接顶点都已经访问过，或者当前深度已经达到图中的总顶点数，但没有形成哈密顿路径或回路，则进行回溯。
回溯时，将当前顶点重新标记为未访问，并返回上一层递归。
通过以上步骤，可以使用哈密顿算法来遍历图中的所有可能的哈密顿路径或回路。
在实际应用中，哈密顿算法可以用于解决旅行推销员问题、电路布线问题等，具有重要的实际意义。
总结起来，哈密顿算法遍历的核心思想是通过深度优先搜索来枚举图中的所有路径，并进行回溯来寻找满足哈密顿路径或回路的条件。
图论算法介绍
if （a[i,k]=1）and (a[k,j]=1) then a[i,j]=1 (a[i,j]=1表示i可达j，a[i,j]=0表示i不可达j）。
var
link，longlink：array[1..20，1..20] of boolean；{ 无向图和无向图的传递闭包。其
中
l o n g l i n k[i,
例如：公路交通图，边以距离w为权。
例
2
2
1
3
1
3
有向完全图 例
245
无向完全图 5
1
例 1
3
6
图与子图
57
32
46
G2
顶点5的度：3 顶点2的度：4
3
6
例 245
1
3
6
G1
顶点2入度：1 出度：3 顶点4入度：1 出度：0
例
路径：1，2，3，5，6，3 路径长度：5
245
简单路径：1，2，3，5
❖ 图 G = (V, E)
V = 顶点集 E = 边集 = V V的子集
结点集V＝｛a， b， c， d｝ 边集E＝｛e1， e2， e3， e4， e5｝ 其中e1＝（a， b）， e2＝（a， c），
e3＝（a， d）， e4＝（b， c）， e5＝（c， d）。
(一)、计算无向图的传递闭包
v1→v2→v4→v8→v5 →v3→v6→v7
算法结构:
调用一次dfs(i)， 可按深度优先搜索 的顺序访问处理结 点i所在的连通分 支（或强连通分 支），dfs(i)的时 间复杂度为W(n2)。 整个图按深度优先 搜索顺序遍历的过 程如下：
显然，为了避免重复访问同一个顶点，必须 记住每个顶点是否被访问过。为此，可设置 一个布尔向量visited[1..n],它的初值为 false，一旦访问了顶点vi，便将visited[i] 置为ture。 图的深度优先搜索是一个递归过程，可以使 用栈来存储那些暂时不访问的邻接点.类似于 树的前序遍历，它的特点是尽可能先对纵深 方向进行搜索，故称之深度优先搜索。
图的遍历算法程序
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //访问第k个顶点
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
//图的邻接矩阵存储结构
typedef struct{
char *vexs; //顶点向量
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
}
//主函数
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n广度优先遍历: ");
for(i=0;i<G.vexnum;i++)
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //访问第k个顶点
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
//图的邻接矩阵存储结构
typedef struct{
char *vexs; //顶点向量
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
}
//主函数
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n广度优先遍历: ");
for(i=0;i<G.vexnum;i++)
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第三部分 最先割技术
第九章 图的遍历
第九章 图的遍历
9．1 引言 9．2 深度优先搜索 9．3 深度优先搜索的应用 9．4 广度优先搜索 9．5 广度优先搜索的应用
9.1 引 言
在一些诸如找出最短路径和最小生成树的图 的算法中，用由它们相应的算法顺序访问顶点 和边。然而，在一些其他算法中，访问顶点的 顺序是不重要的，重要的是，不管输入的图如 何，用一种系统的顺序来访问顶点。在本章中， 我们讨论图遍历的两种方法：深度优先搜索和 广度优先搜索。
1、 根是一个关节点当且仅当在深度优先搜索树中， 它有两个或更多的儿子；
原因：图中不存在连接不同子树顶点的边，删掉根 结点后，生成树就变成了森林。
2、 根以外的其他结点V，如果其某棵子树的根和 子树中的其他结点均没有指向该结点v的祖先的回 边。 或者：根以外的顶点v是一个关节点当且仅当v有 一个儿子w，使得β(w)≥α(v)。
见例9.3。
a
i
d
c
b
g
h
e
f
j
1,1 a
2,1 b
3,3 c
f
6,1
g
7,1
d 4,3
8,8 h
e 5,3
i 9,8
j 10,8
（1）初始化各个顶点；
（2）从a-e开始搜索，一直到e均是正常搜索， 各个数值依次递增增长；
（3）搜索到e时，找到一个回边(e,c)，则e 的β(e)=min{a[c]=3；a[e]=5,β[c]=3}=3；
过程 dfs(v) 1. 标记v已访问；artpoint false; //关节点标记 predfn predfn+1//标记序号
2. α(v) predfn; β(v) predfn //初始化访问序号
3. For 每条边(v,w)∈E 4. If (v,w)为树边 then 5. dfs(w) //深入开始访问后续结点 6. If v=s then //树根结点
我们将假设在这种有向无回路图中有一个入度 是0的唯一的顶点s，如果不是的话，我们可以简 单地添一个新的顶点s，然后让s到所有入度为0的 点加上边。
a
c
e
s
b
d
g f
接下来，我们从顶点s起，简单地对图G执行 深度优先搜索。
当遍历完成时，计数器postdfn定义了一个在 有向无回路图中顶点的反扑排序，于是，为了得 到这个拓扑序，可以在算法DFS中在计数器 postdfn刚好被增加后，加上一个输出步，把输出 结果翻转过来就是我们需要的拓扑序。
3,3 c
f
6,8
g
7,7
d 4,2
8,6 h
e 5,1
i 9,5
j 10,4
2、有向图的情况
有向图中的深度优先搜索导致结果：
一个或多个(有向)生成树，树的多少取决于 初始点。
（1）选择某起始点v，深度优先搜索一棵树， 它由从v出发所有可到达的顶点组成。
（2）没有遍历完所有的顶点，选择另一个顶 点w继续（未访问过顶点），构建一颗从w可到达 的所有未访问顶点组成的树，这个过程继续下去 直到所有的顶点都被访问过。
19. A[count] v
20. End if
（1）首先，算法执行必要的初始化，特别 地，count是关节点的个数，rootdegree是深度优 先搜索树根的度，这在后来决定根是否是关节点 时是需要的。
（2）接着深度优先搜索从根开始着手，对于 每一个访问的顶点v， α(v)和 β(v)用predfn来初始 化。
（4）回退至d点时，该点的β[d]=3;(原来是4);
(5)回退到c点，β[c]=3，由于β[d]>=a[c]，所以 该结点是关节点。
(6)回退到b结点，β[c]>=a[b]，所以b也是一个 关节点。
此（j,h）是一个回边，所以将
β[j]=a[h]=8；
（2）回到i点，该点的β[i]也被改为8； （3）同理，对于h点来讲，其β[h]也被置为8；
此时，由于β[i]>a[h],所以h是关节点； （4）回退到g点,同样存在β[h]>a[g]，所以该点 也是关节点；检测到该点存在回路，所以将其 β[g]值置为其祖先结点的值=1； （5）β[f] β[b]也被置为1,搜索回到a结点，因为 a结点只有一个分支孩子，所以a不是关节点
（注意：测试方法是要依次搜索该点的邻接 点，看是否从某个点访问过它，所以是(n)）
（4）测试顶点w是否标记为未访问，这一步 的执行次数等于顶点v的邻接点数。
这一步执行的总次数，在有向图的情况下等 于它的边数，在无向图的情况下是边数的两倍。
于是，不论是有向图还是无向图，这一步的 耗费是(m)，
（5）算法的总运行时间是：(m+n)。如果图 是连通的或有m≥n,则运行时间简单地为(m)。但 是必须强调的是，图假设是用邻接表表示的。
为关节结点
12.
Endif
13. Else if (v,w)是回边 then //v!=s
β(v) min{β(v), α(w)}
14.
Else do nothing { w是v的父亲}
15. End if
16. End for
17. If artpoint then
18. count count+1
4、在访问过程中，按照上述的深度优先的方 式向前推进，一旦发现某一个顶点X的所有邻 接点都被标志为已访问，访问指针回退至上一 层，继续访问该层没有被访问的其他的子节点。
5、如此往复，直至回退到根节点为止。
算法9.1 DFS
Input: 有向或无向图G=(V,E)。 Output: 在相应的深度优先搜索树中对顶点的前序
算法9.3 STRONGCONNECTCOMP
INPUT:有向图G=(V,E)
OUTPUT:G中的强连通分支
1. 在图G上执行深度优先搜索，对每一个顶点赋
算法9.2 ARTICPOINTS
INPUT:连通无向图G=(V,E)。 OUTPUT:包含G的所有可能关节点的数组 A[1…n]。
1.设s为起始顶点 2.for 每个顶点v∈V 3. 标记v未访问 4.end for //初始化全部结点为没有访问
5.predfn 0;count 0;rootdegree 0 6.dfs(s) //从初始结点开始访问
（3）在搜索从某顶点w退回到v时，要做两件 事，首先，如果发现β(w)比β(v)小，β(v)被设置为 β(w)，其次，如果β(w)≥α(v)，那么这就指出v是 一个关节点，因为从w到v的祖先顶点必须经过v。
这说明在图9.4种，可以看到，从以w为根的子 树到u的任何路径必定包括v，因此v是一个关节点。 以w为根的子树包含一个或多个连通分支。在这 个图中，根u是关节点，因为它的度大于1。
9.3.3 寻找图的关节点
关节点:
在多于两个顶点的无向图G中，存在一个顶点 v，如果有不同于v的两个顶点u和w，在u和w间的 任何路径都必定经过顶点v。
这样，如果G是连通的，移去v和与它关联的边， 将产生G的非连通子图（森林）。一个图如果是 连通的并且没有关节点则称为是双连通的。
由深度优先生成树的特性可以得到如下结论：
（3）重复上述过程，直至所有顶点被访问完 毕。
G的边分成4种类型：
1、树边：深度优先搜索树中的边。如果在搜索边 (v,w)时，w是第一次被访问，则(v,w)是树边。
2、回边：在迄今为止构建的深度优先搜索树中， w是v的祖先，并且当搜索(v,w)时顶点w已被标上 已访问，这样形成的边(v,w)是回边。
9.2.1 深度优先搜索的时间复杂性
(1)顶点v被访问标记为访问的过程，每一个顶 点的调用耗费是(1)。一共需要n个顶点，所以该 过程的总耗费是(n)。 （2）算法的步骤1和步骤3分别耗费(1) 和(n) 时间。//初始化序列号、访问标志 （3）步骤6测试一个顶点是否已标记要耗费(n)。
和后序。
1. predfn 0;postdfn 0 2. For 每个顶点v∈V 3. 标记v未访问 //初始化访问标志
4. End for 5. For 每个顶点v∈V 6. If v未访问 then dfs(v) //调用访问
7. End for
过程 dfs(v) //递归访问
1. 标记v已访问
3、前向边：在迄今为止构建的深度优先搜索树中， w是v的后裔，并且当搜索(v,w)时顶点w被标上已 访问，这种形式的边(v,w)是前向边。
3、横跨边：所有其它的边。
见例9.2。
c
b
a
d
e
f
1,4 a
2,3 b e 3,1
5,6 c
2,2 f
f
d
e
4,2
6,5
3,1
1,4 a
5,6 c
b 4,3
d 6,5
9.3 深度优先搜索的应用
深度优先搜索在图和几何算法中用得很普遍。 在本节中，我们列举它的一些重要应用。
9.3.1 图的无回路性 设G=(V,E)是一个有n个顶点和m条边的有向或
无向图。为了测试G是否至少有一个回路，我们 对G用深度优先搜索，如果在搜索过程中探测到 一条回边，那么G是有回路的，否则G是无回路的。
2、森林（顶点不相连，不能够一次都到达）。
1、无向图的情况分析
设G=(V,E)是无向图，作为遍历的结果，G的边 分成一下两种类型。
树边：深度优先搜索树中的边，如果在搜索边 (v,w)时，w是首次被访问，则边(v,w)是树边。 回边：所有其它的边。
例9.1。
a
i
d
c
b
g
h
e
f
j
1,10 a
2,9 b
a
i
d
c
b
第九章 图的遍历
第九章 图的遍历
9．1 引言 9．2 深度优先搜索 9．3 深度优先搜索的应用 9．4 广度优先搜索 9．5 广度优先搜索的应用
9.1 引 言
在一些诸如找出最短路径和最小生成树的图 的算法中，用由它们相应的算法顺序访问顶点 和边。然而，在一些其他算法中，访问顶点的 顺序是不重要的，重要的是，不管输入的图如 何，用一种系统的顺序来访问顶点。在本章中， 我们讨论图遍历的两种方法：深度优先搜索和 广度优先搜索。
1、 根是一个关节点当且仅当在深度优先搜索树中， 它有两个或更多的儿子；
原因：图中不存在连接不同子树顶点的边，删掉根 结点后，生成树就变成了森林。
2、 根以外的其他结点V，如果其某棵子树的根和 子树中的其他结点均没有指向该结点v的祖先的回 边。 或者：根以外的顶点v是一个关节点当且仅当v有 一个儿子w，使得β(w)≥α(v)。
见例9.3。
a
i
d
c
b
g
h
e
f
j
1,1 a
2,1 b
3,3 c
f
6,1
g
7,1
d 4,3
8,8 h
e 5,3
i 9,8
j 10,8
（1）初始化各个顶点；
（2）从a-e开始搜索，一直到e均是正常搜索， 各个数值依次递增增长；
（3）搜索到e时，找到一个回边(e,c)，则e 的β(e)=min{a[c]=3；a[e]=5,β[c]=3}=3；
过程 dfs(v) 1. 标记v已访问；artpoint false; //关节点标记 predfn predfn+1//标记序号
2. α(v) predfn; β(v) predfn //初始化访问序号
3. For 每条边(v,w)∈E 4. If (v,w)为树边 then 5. dfs(w) //深入开始访问后续结点 6. If v=s then //树根结点
我们将假设在这种有向无回路图中有一个入度 是0的唯一的顶点s，如果不是的话，我们可以简 单地添一个新的顶点s，然后让s到所有入度为0的 点加上边。
a
c
e
s
b
d
g f
接下来，我们从顶点s起，简单地对图G执行 深度优先搜索。
当遍历完成时，计数器postdfn定义了一个在 有向无回路图中顶点的反扑排序，于是，为了得 到这个拓扑序，可以在算法DFS中在计数器 postdfn刚好被增加后，加上一个输出步，把输出 结果翻转过来就是我们需要的拓扑序。
3,3 c
f
6,8
g
7,7
d 4,2
8,6 h
e 5,1
i 9,5
j 10,4
2、有向图的情况
有向图中的深度优先搜索导致结果：
一个或多个(有向)生成树，树的多少取决于 初始点。
（1）选择某起始点v，深度优先搜索一棵树， 它由从v出发所有可到达的顶点组成。
（2）没有遍历完所有的顶点，选择另一个顶 点w继续（未访问过顶点），构建一颗从w可到达 的所有未访问顶点组成的树，这个过程继续下去 直到所有的顶点都被访问过。
19. A[count] v
20. End if
（1）首先，算法执行必要的初始化，特别 地，count是关节点的个数，rootdegree是深度优 先搜索树根的度，这在后来决定根是否是关节点 时是需要的。
（2）接着深度优先搜索从根开始着手，对于 每一个访问的顶点v， α(v)和 β(v)用predfn来初始 化。
（4）回退至d点时，该点的β[d]=3;(原来是4);
(5)回退到c点，β[c]=3，由于β[d]>=a[c]，所以 该结点是关节点。
(6)回退到b结点，β[c]>=a[b]，所以b也是一个 关节点。
此（j,h）是一个回边，所以将
β[j]=a[h]=8；
（2）回到i点，该点的β[i]也被改为8； （3）同理，对于h点来讲，其β[h]也被置为8；
此时，由于β[i]>a[h],所以h是关节点； （4）回退到g点,同样存在β[h]>a[g]，所以该点 也是关节点；检测到该点存在回路，所以将其 β[g]值置为其祖先结点的值=1； （5）β[f] β[b]也被置为1,搜索回到a结点，因为 a结点只有一个分支孩子，所以a不是关节点
（注意：测试方法是要依次搜索该点的邻接 点，看是否从某个点访问过它，所以是(n)）
（4）测试顶点w是否标记为未访问，这一步 的执行次数等于顶点v的邻接点数。
这一步执行的总次数，在有向图的情况下等 于它的边数，在无向图的情况下是边数的两倍。
于是，不论是有向图还是无向图，这一步的 耗费是(m)，
（5）算法的总运行时间是：(m+n)。如果图 是连通的或有m≥n,则运行时间简单地为(m)。但 是必须强调的是，图假设是用邻接表表示的。
为关节结点
12.
Endif
13. Else if (v,w)是回边 then //v!=s
β(v) min{β(v), α(w)}
14.
Else do nothing { w是v的父亲}
15. End if
16. End for
17. If artpoint then
18. count count+1
4、在访问过程中，按照上述的深度优先的方 式向前推进，一旦发现某一个顶点X的所有邻 接点都被标志为已访问，访问指针回退至上一 层，继续访问该层没有被访问的其他的子节点。
5、如此往复，直至回退到根节点为止。
算法9.1 DFS
Input: 有向或无向图G=(V,E)。 Output: 在相应的深度优先搜索树中对顶点的前序
算法9.3 STRONGCONNECTCOMP
INPUT:有向图G=(V,E)
OUTPUT:G中的强连通分支
1. 在图G上执行深度优先搜索，对每一个顶点赋
算法9.2 ARTICPOINTS
INPUT:连通无向图G=(V,E)。 OUTPUT:包含G的所有可能关节点的数组 A[1…n]。
1.设s为起始顶点 2.for 每个顶点v∈V 3. 标记v未访问 4.end for //初始化全部结点为没有访问
5.predfn 0;count 0;rootdegree 0 6.dfs(s) //从初始结点开始访问
（3）在搜索从某顶点w退回到v时，要做两件 事，首先，如果发现β(w)比β(v)小，β(v)被设置为 β(w)，其次，如果β(w)≥α(v)，那么这就指出v是 一个关节点，因为从w到v的祖先顶点必须经过v。
这说明在图9.4种，可以看到，从以w为根的子 树到u的任何路径必定包括v，因此v是一个关节点。 以w为根的子树包含一个或多个连通分支。在这 个图中，根u是关节点，因为它的度大于1。
9.3.3 寻找图的关节点
关节点:
在多于两个顶点的无向图G中，存在一个顶点 v，如果有不同于v的两个顶点u和w，在u和w间的 任何路径都必定经过顶点v。
这样，如果G是连通的，移去v和与它关联的边， 将产生G的非连通子图（森林）。一个图如果是 连通的并且没有关节点则称为是双连通的。
由深度优先生成树的特性可以得到如下结论：
（3）重复上述过程，直至所有顶点被访问完 毕。
G的边分成4种类型：
1、树边：深度优先搜索树中的边。如果在搜索边 (v,w)时，w是第一次被访问，则(v,w)是树边。
2、回边：在迄今为止构建的深度优先搜索树中， w是v的祖先，并且当搜索(v,w)时顶点w已被标上 已访问，这样形成的边(v,w)是回边。
9.2.1 深度优先搜索的时间复杂性
(1)顶点v被访问标记为访问的过程，每一个顶 点的调用耗费是(1)。一共需要n个顶点，所以该 过程的总耗费是(n)。 （2）算法的步骤1和步骤3分别耗费(1) 和(n) 时间。//初始化序列号、访问标志 （3）步骤6测试一个顶点是否已标记要耗费(n)。
和后序。
1. predfn 0;postdfn 0 2. For 每个顶点v∈V 3. 标记v未访问 //初始化访问标志
4. End for 5. For 每个顶点v∈V 6. If v未访问 then dfs(v) //调用访问
7. End for
过程 dfs(v) //递归访问
1. 标记v已访问
3、前向边：在迄今为止构建的深度优先搜索树中， w是v的后裔，并且当搜索(v,w)时顶点w被标上已 访问，这种形式的边(v,w)是前向边。
3、横跨边：所有其它的边。
见例9.2。
c
b
a
d
e
f
1,4 a
2,3 b e 3,1
5,6 c
2,2 f
f
d
e
4,2
6,5
3,1
1,4 a
5,6 c
b 4,3
d 6,5
9.3 深度优先搜索的应用
深度优先搜索在图和几何算法中用得很普遍。 在本节中，我们列举它的一些重要应用。
9.3.1 图的无回路性 设G=(V,E)是一个有n个顶点和m条边的有向或
无向图。为了测试G是否至少有一个回路，我们 对G用深度优先搜索，如果在搜索过程中探测到 一条回边，那么G是有回路的，否则G是无回路的。
2、森林（顶点不相连，不能够一次都到达）。
1、无向图的情况分析
设G=(V,E)是无向图，作为遍历的结果，G的边 分成一下两种类型。
树边：深度优先搜索树中的边，如果在搜索边 (v,w)时，w是首次被访问，则边(v,w)是树边。 回边：所有其它的边。
例9.1。
a
i
d
c
b
g
h
e
f
j
1,10 a
2,9 b
a
i
d
c
b