|
|
|
|
|
从图G中任一个顶点v出发，深度优先遍历（DFS）的算法步骤如下。
|
|
|
|
|
|
（2）访问p顶点，并使p指向与p顶点相邻接的且尚未被访问过的顶点。
|
|
|
|
（3）若p不空，则重复步骤（2）；否则执行步骤（4）。
|
|
|
|
（4）沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的邻接顶点，然后重复步骤（2），直至所有的顶点均被访问为止。
|
|
|
|
这个算法的特点是尽可能先对纵深方向搜索，因此可以很容易得到其遍历的递归算法。
|
|
|
|
深度优先遍历图的过程实质上是对某个顶点查找其邻接节点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n2)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。
|
|
|
|
|
|
广度优先遍历（BFS）的遍历过程是：假设从图中某一个顶点v出发，在访问v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使"先被访问的顶点的邻接点"先于"后被访问的顶点的邻接点"被访问，直至图中所有已被访问过的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选其中一个作为起点，重复上述过程，直至图中所有的顶点都被访问到为止。
|
|
|
|
广度优先遍历图的特点是尽可能先进行横向搜索，即最先访问的顶点的邻接点亦先被访问。
|
|
|
京公网安备 11010502032051号 | 营业执照