母婴网站建设前期规划,wordpress汉化主体,江西最新消息,一个域名权重3如果做网站的话权重会降为0吗转载#xff1a;https://www.cnblogs.com/skywang12345/p/3711483.html 深度优先搜索 1. 深度优先搜索介绍
图的深度优先搜索(Depth First Search)#xff0c;和树的先序遍历比较类似。
它的思想#xff1a;假设初始状态是图中所有顶点均未被访问#xff0c;则从某个顶点…
转载https://www.cnblogs.com/skywang12345/p/3711483.html 深度优先搜索 1. 深度优先搜索介绍
图的深度优先搜索(Depth First Search)和树的先序遍历比较类似。
它的思想假设初始状态是图中所有顶点均未被访问则从某个顶点v出发首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到则另选一个未被访问的顶点作起始点重复上述过程直至图中所有顶点都被访问到为止。
显然深度优先搜索是一个递归的过程。 2. 深度优先搜索图解
2.1 无向图的深度优先搜索
下面以无向图为例来对深度优先搜索进行演示。 对上面的图G1进行深度优先遍历从顶点A开始。 第1步访问A。
第2步访问(A的邻接点)C。 在第1步访问A之后接下来应该访问的是A的邻接点即C,D,F中的一个。但在本文的实现中顶点ABCDEFG是按照顺序存储C在D和F的前面因此先访问C。
第3步访问(C的邻接点)B。 在第2步访问C之后接下来应该访问C的邻接点即B和D中一个(A已经被访问过就不算在内)。而由于B在D之前先访问B。
第4步访问(C的邻接点)D。 在第3步访问了C的邻接点B之后B没有未被访问的邻接点因此返回到访问C的另一个邻接点D。
第5步访问(A的邻接点)F。 前面已经访问了A并且访问完了A的邻接点B的所有邻接点(包括递归的邻接点在内)因此此时返回到访问A的另一个邻接点F。
第6步访问(F的邻接点)G。
第7步访问(G的邻接点)E。 因此访问顺序是A - C - B - D - F - G - E 2.2 有向图的深度优先搜索
下面以有向图为例来对深度优先搜索进行演示。 对上面的图G2进行深度优先遍历从顶点A开始。 第1步访问A。
第2步访问B。 在访问了A之后接下来应该访问的是A的出边的另一个顶点即顶点B。
第3步访问C。 在访问了B之后接下来应该访问的是B的出边的另一个顶点即顶点C,E,F。在本文实现的图中顶点ABCDEFG按照顺序存储因此先访问C。
第4步访问E。 接下来访问C的出边的另一个顶点即顶点E。
第5步访问D。 接下来访问E的出边的另一个顶点即顶点B,D。顶点B已经被访问过因此访问顶点D。
第6步访问F。 接下应该回溯访问A的出边的另一个顶点F。
第7步访问G。 因此访问顺序是A - B - C - E - D - F - G
