常见的网页布局有哪些,上海公司网站seo,做外贸一般总浏览的网站,有户型图怎么免费设计装修本章会先对图的深度优先搜索和广度优先搜索进行介绍#xff0c;然后再给出C/C/Java的实现。
一、深度优先搜索的图文介绍
1. 深度优先搜索介绍
图的深度优先搜索(Depth First Search)#xff0c;和树的先序遍历比较类似。
它的思想#xff1a;假设初始状态是图中所有顶点…本章会先对图的深度优先搜索和广度优先搜索进行介绍然后再给出C/C/Java的实现。
一、深度优先搜索的图文介绍
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
二、广度优先搜索的图文介绍
1. 广度优先搜索介绍
广度优先搜索算法(Breadth First Search)又称为宽度优先搜索或横向优先搜索简称BFS。
它的思想是从图中某顶点v出发在访问了v之后依次访问v的各个未曾访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问则需要另选一个未曾被访问过的顶点作为新的起始点重复上述过程直至图中所有顶点都被访问到为止。
换句话说广度优先搜索遍历图的过程是以v为起点由近至远依次访问和v有路径相通且路径长度为1,2...的顶点。
2. 广度优先搜索图解
2.1 无向图的广度优先搜索
下面以无向图为例来对广度优先搜索进行演示。还是以上面的图G1为例进行说明。
第1步访问A。 第2步依次访问C,D,F。 在访问了A之后接下来访问A的邻接点。前面已经说过在本文实现中顶点ABCDEFG按照顺序存储的C在D和F的前面因此先访问C。再访问完C之后再依次访问D,F。 第3步依次访问B,G。 在第2步访问完C,D,F之后再依次访问它们的邻接点。首先访问C的邻接点B再访问F的邻接点G。 第4步访问E。 在第3步访问完B,G之后再依次访问它们的邻接点。只有G有邻接点E因此访问G的邻接点E。
因此访问顺序是A - C - D - F - B - G - E
2.2 有向图的广度优先搜索
下面以有向图为例来对广度优先搜索进行演示。还是以上面的图G2为例进行说明。
第1步访问A。 第2步访问B。 第3步依次访问C,E,F。 在访问了B之后接下来访问B的出边的另一个顶点即C,E,F。前面已经说过在本文实现中顶点ABCDEFG按照顺序存储的因此会先访问C再依次访问E,F。 第4步依次访问D,G。 在访问完C,E,F之后再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问C的已经全部访问过了那么就只剩下E,F先访问E的邻接点D再访问F的邻接点G。
因此访问顺序是A - B - C - E - F - D - G
三、搜索算法的源码
这里分别给出邻接矩阵无向图、邻接表无向图、邻接矩阵有向图、邻接表有向图的C/C/Java搜索算法源码。这里就不再对源码进行说明please RTFSC参考源码中的注释进行了解。
1. C语言源码 1.1 邻接矩阵实现的无向图(matrixudg.c) 1.2 邻接表实现的无向图(listudg.c) 1.3 邻接矩阵实现的有向图(matrixdg.c) 1.4 邻接表实现的有向图(listdg.c)
2. C源码 2.1 邻接矩阵实现的无向图(MatrixUDG.cpp) 2.2 邻接表实现的无向图(ListUDG.cpp) 2.3 邻接矩阵实现的有向图(MatrixDG.cpp) 2.4 邻接表实现的有向图(ListDG.cpp)
3. Java源码 3.1 邻接矩阵实现的无向图(MatrixUDG.java) 3.2 邻接表实现的无向图(ListUDG.java) 3.3 邻接矩阵实现的有向图(MatrixDG.java) 3.4 邻接表实现的有向图(ListDG.java)
