一、二叉树深度优先（DFS）和广度优先（BFS）搜索算法

树的相关概念参见

（1）深度优先搜索算法（Depth First Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

讯享网

A 是第一个访问的，然后顺序是 B、D，然后是 E。接着再是 C、F、G。那么，怎么样才能来保证这个访问的顺序呢？分析一下，在遍历了根结点后，就开始遍历左子树，最后才是右子树。因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序，由此可以先将右子树压栈，然后再对左子树压栈，这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。

深度优先遍历代码片段：

（2）广度优先搜索算法（Breadth First Search），又叫宽度优先搜索，或横向优先搜索。是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。

如下图所示的二叉树：

A 是第一个访问的，然后顺序是 B、C，然后再是 D、E、F、G。那么，怎样才能来保证这个访问的顺序呢？借助队列数据结构，由于队列是先进先出的顺序，因此可以先将左子树入队，然后再将右子树入队。这样一来，左子树结点就存在队头，可以先被访问到。

广度优先遍历代码片段：

二、图的深度优先（DFS）和广度优先（BFS）搜索算法

在介绍图的搜索之前，有必要先了解计算机中图的存储方式。图的存储表示方法很多，这里介绍两种最常用的方法。至于具体选择哪一种表示法，主要取决于具体的应用和欲施加的操作。为了适合用C语言描述，以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v₀，v_i，…，V_n-1}。
（1）图的邻接矩阵表示法
1．图的邻接矩阵表示法     　

在图的邻接矩阵表示法中： 　

　　① 用邻接矩阵表示顶点间的相邻关系 　

　　② 用一个顺序表来存储顶点信息

2．图的邻接矩阵(Adacency Matrix)     　

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：   

   
【例】下图中无向图G₅和有向图G₆的邻接矩阵分别为A_l和A₂。

3．网络的邻接矩阵     　

若G是网络，则邻接矩阵可定义为：    

        
其中：      

　　w_ij表示边上的权值；      

　　∞表示一个计算机允许的、大于所有边上权值的数。

【例】下面带权图的两种邻接矩阵分别为A₃和A₄。

       
4．图的邻接矩阵存储结构形式说明   

注意： 　   

　　① 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。     　

　　② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。     　

　　③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。     　

　　④ 邻接矩阵表示法的空间复杂度S(n)=0(n²)。

5．建立无向网络的算法。

该算法的执行时间是0(n+n²+e)。由于e<n²，算法的时间复杂度是0(n²)。

（2）图的邻接表表示法
　　图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点v_i，该方法把所有邻接于v_i的顶点v_j链成一个带头结点的单链表，这个单链表就称为顶点v_i的邻接表(Adjacency
List)。
1． 邻接表的结点结构
（1）表结点结构

邻接表中每个表结点均有两个域:
　　① 邻接点域adjvex：存放与vi相邻接的顶点v_j的序号j。
　　② 链域next：将邻接表的所有表结点链在一起。
注意：若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。

（2）头结点结构

顶点v_i邻接表的头结点包含两个域：
　　① 顶点域vertex：存放顶点v_i的信息
　　② 指针域firstedge：v_i的邻接表的头指针。

注意：
　　 ① 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。
    　② 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。
2．无向图的邻接表
　　对于无向图，v_i的邻接表中每个表结点都对应于与v_i相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。
【例】对于无向图G₅，其邻接表表示如下面所示，其中顶点v₀的边表上三个表结点中的顶点序号分别为1、2和3，它们分别表示关联于v₀的三条边(v₀，v₁)，(v₀，v₂)和(v₀，v₃)。

注意：n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。
3．有向图的邻接表
　　对于有向图，v_i的邻接表中每个表结点都对应于以v_i为始点射出的一条边。因此，将有向图的邻接表称为出边表。
【例】有向图G₆的邻接表表示如下面(a)图所示，其中顶点v₁的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v₁射出的两条边(简称为v₁的出边)：<v₁，v₀>和<v₁，v₄>。

注意：n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。
4．有向图的逆邻接表
在有向图中，为图中每个顶点v_i建立一个入边表的方法称逆邻接表表示法。
入边表中的每个表结点均对应一条以v_i为终点(即射入v_i)的边。
【例】G₆的逆邻表如上面(b)图所示，其中v₀的人边表上两个表结点1和3分别表示射人v₀的两条边(简称为v₀的入边)：<v₁，v₀>和<v₃，v₀>。
注意：n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。

(2)建立无向图的邻接表算法

该算法的时间复杂度是O(n+e)。
注意：

　　①建立有向图的邻接表更简单，每当读人一个顶点对序号<i,j>时，仅需生成一个邻接序号为j的边表结点，将其插入到v_j的出边表头部即可。
　　② 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。

（3）图的遍历

深度优先遍历(Depth-First Traversal)

1．图的深度优先遍历的递归定义

2、深度优先搜索的过程
    　设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

3、深度优先遍历的递归算法

4、算法分析
　　对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。
　　当访问某顶点v_i时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，在邻接矩阵上共需检查n²个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。
所以，DFSTraverse的时间复杂度为O(n²) （调用DFSM）或0(n+e)（调用DFS）。

5、深度优先遍历的非递归算法

广度优先遍历(Breadth-FirstTraversal)

1、广度优先遍历的递归定义     　

设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。     　

若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。     　

广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。

2、广度优先搜索过程    　

在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，…，xs和y1，y2，…，yt。     　

为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，…，xs和y1，y2，…，yt，对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至多只有一次人队。

3、广度优先搜索算法

4、算法分析
　对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次。广度优先遍历(BFSTraverse)图的时间复杂度和DFSTraverse算法相同。
　当图是连通图时，BFSTraverse算法只需调用一次BFS或BFSM即可完成遍历操作，此时BFS和BFSM的时间复杂度分别为O(n+e)和0(n²)。

&nbsp;

&nbsp;【参考】http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/tu/tu7.1.1.htm

&nbsp;