论文部分内容阅读
【摘要】图算法是数据结构与算法中一个比较重要的内容，而图的遍历算法是图算法的基础，也就是说其他的图算法都是在遍历算法的基础之上加以改进。本篇论文主要介绍了两种图的遍历算法，分别是图的深度优先遍历和图的宽度优先遍历。在介绍图的遍历算法之前，先介绍了图的基础知识，其中包括图的定义、邻接点和关联边、顶点的度、（强）连通图和图的表示方法。介绍图的遍历算法时，依次介绍了遍历算法的基本步骤、程序框图和伪代码。最后对全文做总结，并对图的遍历算法在未来如何应用的问题进行了展望。
【关键词】深度优先遍历 宽度优先遍历
【中图分类号】G63 【文献标识码】A 【文章编号】2095-3089（2018）40-0222-02
1.引言
遍历算法是目前计算机领域中的一个重要的研究方向，一个问题的求解就是从最开始的状态，利用已经存在的规则和条件改变当前状态，直到把当前状态变为最终目的状态，把中间出现的状态全部连接起来，变成一条遍历路径的过程。通过图的遍历，我们可以找到这条路径[1]。
图的遍历算法主要有两种，一种是按照深度优先的顺序展开遍历的算法，也就是深度优先遍历[2];另一种是按照宽度优先的顺序展开遍历的算法，也就是宽度优先遍历[3]。
宽度优先遍历是沿着图的深度遍历图的所有节点，每次遍历都会沿着当前节点的邻接点遍历，直到所有点全部遍历完成。如果当前节点的所有邻接点都遍历过了，则回溯到上一个节点，重复这一过程一直到已访问从源节点可达的所有节点为止。如果还存在没有被访问的节点，则选择其中一个节点作为源节点并重复以上过程，直到所有节点都被访问为止。利用图的深度优先搜索可以获得很多额外的信息，也可以解决很多图论的问题。
宽度優先遍历又名广度优先遍历。通过沿着图的宽度遍历图的节点，如果所有节点均被访问，算法随即终止。宽度优先遍历的实现一般需要一个队列来辅助完成。宽度优先遍历和深度优先遍历一样也是一种盲目的遍历方法。也就是说，宽度遍历算法并不使用经验法则算法，并不考虑结果的可能地址，只是彻底地遍历整张图，直到找到结果为止。
2.图的基础知识
2.1图的定义
数据结构中图是有两部分组成的，一部分是边集合，另一部分是点集合。所以图可以记为Graph=（V， R），在该公式中V={x|x∈某个数据对象}，可以看作是点的集合;R={（u，v）|u，v∈V}∈V是边的集合，如果括号为<>，则说明边是有向边。例：边<u，v>，即为由节点u指向节点v的边。
2.2邻接点和关联边
若（vi，vj）是一条无向边，则称顶点vi和vj互为邻接点，并称边（vi，vj）关联于顶点vi和vj。
例如：边e=（v1，v2）， 则称顶点v1、v2关联边e。
2.3顶点的度
对于一个无向图来讲，顶点的度是指一个顶点v的度是与它相关联的边的条数，记为TD（v）。
对于一个有向图来讲，顶点的度分为入度和出度。顶点v的入度是以v为终点的有向边的条数，记为ID（v）;顶点v的出度是以v为始点的有向边的条数，记作OD（v）。
2.4（强）连通图
若在一个无向图Graph=（V， R）中，任意两个顶点u，v都存在从u到v的一条路径，则称G是连通图。如果图Graph=（V， R）是有向图，同时满足对任意两个顶点u，v都存在从u到v的一条路径，则称G是强连通图。
2.5图的邻接矩阵表示法
若图用邻接矩阵表示，则包含两部分，一部分是顶点表，包含各个顶点的信息;另一部分是邻接矩阵，用于记录边信息。
设图 A = （V， R）是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 Matrix[n][n]，定义为：
Matrix[i][j]=1，如果<i，j>∈E或者（i，j）∈E0，否则
图的邻接矩阵表示法具有如下特点：
（1）无向图邻接矩阵关于一条对角线对称，是对称矩阵，同一条边表示了两次;
（2）顶点v的度：等于二维数组对应行（或列）中1的个数;
（3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1;
（4）顶点不变，在图中增加、删除边的过程：对二维数组对应分量赋值1或清0;
下图是邻接矩阵表示实例。
2.6图的邻接表表示法
邻接表是图的链式存储结构。通常将邻接表中的顶点按顺序存储在一维数组当中;然后将相关联的点用线性表存储起来。用邻接表存储可以较大程度的节约空间，减少不必要的浪费，缺陷是用邻接表储存需要判断两个顶点之间的关系，降低了效率。
下图是邻接表表示实例。
3.深度优先遍历
3.1基本步骤
深度优先遍历的基本步骤为：将标记数组初始化为0;然后从图的第一个顶点一般是V1开始访问该点，并将其对应的标记数组置为1，表示该点已被访问过;获得V1的所有邻接点，然后依次从V1未访问过的邻接顶点出发，依次深度遍历图中的V1沿边所能到达的所有节点，重复上述过程，直至图中所有顶点对应的标记数组都被置为1，即所有的顶点都已经被访问过为止。
3.2程序框图
图的深度优先遍历算法程序框图如下：
3.3伪代码
图的深度优先搜索伪代码如下：
1）初始化标记数组visited[n]={0};
2）访问顶点v; visited[v]=1;
3）w=顶点v的第一个邻接点; 4）while（w存在）
if（w未被访问）
从顶点w出发递归执行该算法;
w=顶点v的下一个邻接点;
4.广度优先遍历
4.1基本步骤
寬度优先遍历的基本步骤为：将标记数组初始化为0;然后从图的第一个顶点一般是V1开始访问该点，获得V1节点的所有邻接点，然后分别访问这些邻接点，并且获取这些点的邻接点，重复上述过程一直到所有顶点都已经被访问过。
4.2程序框图
图的宽度优先遍历算法程序框图如图4。
4.3伪代码
图的宽度优先搜索伪代码如下：
1）初始化队列Q;visited[n]={0};
2）访问顶点v;visited[v]=1;顶点v入队列Q;
3）While（队列Q非空）
v=队列Q的对头元素出队;
w=顶点v的第一个邻接点;
while（w存在）
如果未访问，则访问顶点w;
visited[w]=1;
顶点w如队列Q;
W=顶点v的下一个邻接点;
5.总结与展望
本文主要介绍了图的深度优先遍历和宽度优先遍历。这两种遍历算法是比较基础的图算法，通过深入详尽地研究两种算法，可以以此作为突破口了解其它的算法。随着互联网的发展，遍历算法已经在日常的各种领域有了大量的应用。遍历的方法可以解决生活中的许多问题，例如邮递员问题。在人工智能高速发展的时代，可以预见遍历算法一定会有更加深入的应用。将遍历算法引入人工智能领域并且使其得到充分的发展，一定会带来意想不到的收获。
参考文献：
[1]龚建华. 深度优先搜索算法及其改进[J].现代电子技术， 2007， 30（22）：90-92.
[2]Y Minamide . Depth First Search[J]. 2004.
[3]A Bundy， L Wallen. Breadth-First Search[M]// Catalogue of Artificial Intelligence Tools. Springer Berlin Heidelberg， 1984.
【关键词】深度优先遍历 宽度优先遍历
【中图分类号】G63 【文献标识码】A 【文章编号】2095-3089（2018）40-0222-02
1.引言
遍历算法是目前计算机领域中的一个重要的研究方向，一个问题的求解就是从最开始的状态，利用已经存在的规则和条件改变当前状态，直到把当前状态变为最终目的状态，把中间出现的状态全部连接起来，变成一条遍历路径的过程。通过图的遍历，我们可以找到这条路径[1]。
图的遍历算法主要有两种，一种是按照深度优先的顺序展开遍历的算法，也就是深度优先遍历[2];另一种是按照宽度优先的顺序展开遍历的算法，也就是宽度优先遍历[3]。
宽度优先遍历是沿着图的深度遍历图的所有节点，每次遍历都会沿着当前节点的邻接点遍历，直到所有点全部遍历完成。如果当前节点的所有邻接点都遍历过了，则回溯到上一个节点，重复这一过程一直到已访问从源节点可达的所有节点为止。如果还存在没有被访问的节点，则选择其中一个节点作为源节点并重复以上过程，直到所有节点都被访问为止。利用图的深度优先搜索可以获得很多额外的信息，也可以解决很多图论的问题。
宽度優先遍历又名广度优先遍历。通过沿着图的宽度遍历图的节点，如果所有节点均被访问，算法随即终止。宽度优先遍历的实现一般需要一个队列来辅助完成。宽度优先遍历和深度优先遍历一样也是一种盲目的遍历方法。也就是说，宽度遍历算法并不使用经验法则算法，并不考虑结果的可能地址，只是彻底地遍历整张图，直到找到结果为止。
2.图的基础知识
2.1图的定义
数据结构中图是有两部分组成的，一部分是边集合，另一部分是点集合。所以图可以记为Graph=（V， R），在该公式中V={x|x∈某个数据对象}，可以看作是点的集合;R={（u，v）|u，v∈V}∈V是边的集合，如果括号为<>，则说明边是有向边。例：边<u，v>，即为由节点u指向节点v的边。
2.2邻接点和关联边
若（vi，vj）是一条无向边，则称顶点vi和vj互为邻接点，并称边（vi，vj）关联于顶点vi和vj。
例如：边e=（v1，v2）， 则称顶点v1、v2关联边e。
2.3顶点的度
对于一个无向图来讲，顶点的度是指一个顶点v的度是与它相关联的边的条数，记为TD（v）。
对于一个有向图来讲，顶点的度分为入度和出度。顶点v的入度是以v为终点的有向边的条数，记为ID（v）;顶点v的出度是以v为始点的有向边的条数，记作OD（v）。
2.4（强）连通图
若在一个无向图Graph=（V， R）中，任意两个顶点u，v都存在从u到v的一条路径，则称G是连通图。如果图Graph=（V， R）是有向图，同时满足对任意两个顶点u，v都存在从u到v的一条路径，则称G是强连通图。
2.5图的邻接矩阵表示法
若图用邻接矩阵表示，则包含两部分，一部分是顶点表，包含各个顶点的信息;另一部分是邻接矩阵，用于记录边信息。
设图 A = （V， R）是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 Matrix[n][n]，定义为：
Matrix[i][j]=1，如果<i，j>∈E或者（i，j）∈E0，否则
图的邻接矩阵表示法具有如下特点：
（1）无向图邻接矩阵关于一条对角线对称，是对称矩阵，同一条边表示了两次;
（2）顶点v的度：等于二维数组对应行（或列）中1的个数;
（3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1;
（4）顶点不变，在图中增加、删除边的过程：对二维数组对应分量赋值1或清0;
下图是邻接矩阵表示实例。
2.6图的邻接表表示法
邻接表是图的链式存储结构。通常将邻接表中的顶点按顺序存储在一维数组当中;然后将相关联的点用线性表存储起来。用邻接表存储可以较大程度的节约空间，减少不必要的浪费，缺陷是用邻接表储存需要判断两个顶点之间的关系，降低了效率。
下图是邻接表表示实例。
3.深度优先遍历
3.1基本步骤
深度优先遍历的基本步骤为：将标记数组初始化为0;然后从图的第一个顶点一般是V1开始访问该点，并将其对应的标记数组置为1，表示该点已被访问过;获得V1的所有邻接点，然后依次从V1未访问过的邻接顶点出发，依次深度遍历图中的V1沿边所能到达的所有节点，重复上述过程，直至图中所有顶点对应的标记数组都被置为1，即所有的顶点都已经被访问过为止。
3.2程序框图
图的深度优先遍历算法程序框图如下：
3.3伪代码
图的深度优先搜索伪代码如下：
1）初始化标记数组visited[n]={0};
2）访问顶点v; visited[v]=1;
3）w=顶点v的第一个邻接点; 4）while（w存在）
if（w未被访问）
从顶点w出发递归执行该算法;
w=顶点v的下一个邻接点;
4.广度优先遍历
4.1基本步骤
寬度优先遍历的基本步骤为：将标记数组初始化为0;然后从图的第一个顶点一般是V1开始访问该点，获得V1节点的所有邻接点，然后分别访问这些邻接点，并且获取这些点的邻接点，重复上述过程一直到所有顶点都已经被访问过。
4.2程序框图
图的宽度优先遍历算法程序框图如图4。
4.3伪代码
图的宽度优先搜索伪代码如下：
1）初始化队列Q;visited[n]={0};
2）访问顶点v;visited[v]=1;顶点v入队列Q;
3）While（队列Q非空）
v=队列Q的对头元素出队;
w=顶点v的第一个邻接点;
while（w存在）
如果未访问，则访问顶点w;
visited[w]=1;
顶点w如队列Q;
W=顶点v的下一个邻接点;
5.总结与展望
本文主要介绍了图的深度优先遍历和宽度优先遍历。这两种遍历算法是比较基础的图算法，通过深入详尽地研究两种算法，可以以此作为突破口了解其它的算法。随着互联网的发展，遍历算法已经在日常的各种领域有了大量的应用。遍历的方法可以解决生活中的许多问题，例如邮递员问题。在人工智能高速发展的时代，可以预见遍历算法一定会有更加深入的应用。将遍历算法引入人工智能领域并且使其得到充分的发展，一定会带来意想不到的收获。
参考文献：
[1]龚建华. 深度优先搜索算法及其改进[J].现代电子技术， 2007， 30（22）：90-92.
[2]Y Minamide . Depth First Search[J]. 2004.
[3]A Bundy， L Wallen. Breadth-First Search[M]// Catalogue of Artificial Intelligence Tools. Springer Berlin Heidelberg， 1984.