深度优先搜索适用于(深度优先搜索是什么)-东辰安华生活网

深度优先搜索适用于(深度优先搜索是什么),本文通过数据整理汇集了深度优先搜索适用于(深度优先搜索是什么)相关信息，下面一起看看。

1.深度优先搜索简介

图的深度优先搜索类似于树的前序遍历。

其思想是：假设初始状态下图中所有顶点都没有被访问，从某个顶点V开始，先访问该顶点，然后依次从其所有未被访问的邻点开始，先对遍历图进行深度搜索，直到图中所有路径为V的顶点都被访问。如果此时还有其他顶点没有被访问过，则选择另一个没有被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问过。

显然，深度优先搜索是一个递归过程。

2.深度优先搜索图

2.1无向图的深度优先搜索

拿下面的无向图作为演示深度优先搜索的例子。

上面的图G1是从顶点A开始深度遍历的.

第一步：拜访a。

第二步：访问(A的相邻点)c。

第一步访问A后，接下来要访问的是A的邻点，也就是丙、丁、己但是在本文的实现中，顶点ABCDEFG是按顺序存储的，C排在d和F # ，所以先访问C。

第三步：访问(C的邻点)b。

第二步访问C后，下一步是访问C的邻点，即b和D # (A已经被访问过了，所以它不t计数)。而且因为b在d之前，所以先访问b。

第四步：访问(C) D的邻点。

第三步，访问完C的邻点B后，没有没有访问过的邻点B；因此，它返回到入口C的另一个相邻点d.

第五步：访问(A的邻点)f。

a已经被较早地访问过，并且所有的邻点一s邻点B(包括递归邻点)被访问过；因此，此时，它返回到访问A的另一个相邻点F.

第六步：访问(F) G的邻点。

第七步：访问(G的相邻点)e。

所以访问的顺序是：A-C-B-D-F-G-E

2.2有向图的深度优先搜索

拿下面的有向图作为演示深度优先搜索的例子。

从顶点A开始，首先对上面的图G2进行深度遍历.

第一步：拜访a。

第二步：拜访b。

访问完A，接下来要访问的是A的边的另一个顶点，即顶点b。

第三步：访问c。

访问完B，接下来要访问的是B的边的另一个顶点，即顶点C，E，F E，F，本文实现的图中，顶点ABCDEFG是按顺序存储的，所以先访问C。

第四步：访问e。

接下来，访问C的边的另一个顶点，即顶点e。

第五步：拜访d。

接下来，访问E的边的另一个顶点，即顶点B，d。顶点B已经被访问过，所以访问顶点d。

第六步：拜访f。

接下来，我们应该回到访问A # 的边的另一个顶点F；

第七步：拜访g。

所以访问的顺序是：A-B-C-E-D-F-G

广度优先搜索的图形介绍

1.广度优先搜索简介

广度优先搜索算法，也称为广度优先搜索还是水平优先搜索缩写为BFS。

它的思想是：从图中的一个顶点V开始，在访问V之后，依次访问V的所有没有访问过的邻点，然后从这些邻点分别访问它们的邻点，这样首先被访问的顶点的相邻点在随后被访问的顶点的相邻点之前被访问，直到图中被访问的顶点的所有相邻点都被访问。如果此时图中还有未被访问过的顶点，则需要选择另一个未被访问过的顶点作为新的起点，重复上述过程，直到图中的所有顶点都被访问过。

换句话说，广度优先搜索遍历图的过程是从V开始，由近及远，依次访问路径长度为1，2，它们与v相连。

2.广度优先搜索图

2.1无向图的广度优先搜索

以下面的无向图为例，演示广度优先搜索。以上图G1为例。

第一步：拜访a。

第二步：依次拜访C、D、F。

访问A后，访问下一个A的相邻点。如前所述，在本文的实现中，顶点ABCDEFG是按顺序存储的，C排在d和F # 因此，首先访问C。参观完C，依次参观D和F。

第三步：依次拜访B和G。

在步骤2中访问C、D和F之后，依次访问它们的相邻点。先访问C的邻点B，再访问f的邻点G。

第四步：访问e。

在步骤3中访问B和G之后，依次访问它们的相邻点。只有g有邻点e，所以取g的邻点e。

所以访问的顺序是：A-C-D-F-B-G-E。