您现在所在位置: 首页 > IT知识库

数据结构之图的遍历,一篇文章get全部考点

发布时间:2022-01-12点击数:

图的概念

      举个例子,假设你的微信朋友圈中有若干好友:张三、李四、王五、赵六、七大姑、八大姨。


      而你七大姑的微信号里,又有若干好友:你、八大姨、Jack、Rose。


      微信中,许许多多的用户组成了一个多对多的朋友关系网,这个关系网就是数据结构当中的 图(Graph) 。

       图,是一种比树更为复杂的数据结构。

       树的节点之间是一对多的关系,并且存在父与子的层级划分;而图的顶点(注意,这里不叫节点)之间是多对多关系,且所有顶点都平等,无所谓谁是父谁是子。


图的术语


      在图中,最基本的单元是顶点(vertex),相当于树中的节点。顶点之间的关联关系,被称为边(edge)。

      在有些图中,每一条边并不是完全等同的。比如地铁线路,从A站到B站的距离是3公里,从B站到C站的距离是5公里……这样就引入一个新概念: 边的权重(Weight) 。涉及到权重的图,被称为 带权图(Weighted Graph) 。


      还有一种图,顶点之间的关联并不是完全对称的。还拿微信来举例,你的好友列表里有我,但我的好友列表里未必有你。这样一来,顶点之间的边就有了方向的区分,这种带有方向的图被称为 有向图 。


图的存储结构

      01 邻接矩阵

      拥有n个顶点的图,它所包含的连接数量最多是n(n-1)个。因此,要表达各个顶点之间的关联关系,最清晰易懂的方式是使用二维数组(矩阵)。

      具体如何表示呢?我们首先来看看无向图的矩阵表示:


      如图所示,顶点0和顶点1之间有边关联,那么矩阵中的元素A[0][1]与A[1][0]的值就是1;顶点1和顶点2之间没有边关联,那么矩阵中的元素A[1][2]与A[2][1]的值就是0。

      像这样表达图中顶点关联关系的矩阵,就叫 邻接矩阵 。


      02  邻接表

      为了解决邻接矩阵占用空间的问题,人们想到了另一种图的表示方法:邻接表。


       在邻接表中,图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点。

      图的表示方法有很多种。包括邻接矩阵、邻接表、逆邻接表、十字链表,这里不过多介绍,有兴趣的同学可以自己了解下。


图的遍历


      从图的某个顶点出发,访问图中的所有顶点,且使每个顶点仅被访问一次。这一过程叫做 图的遍历 。


      01  深度优先搜索

      图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。简称DFS

      深度优先搜索的思想:

      1、访问顶点v;

      2、依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

      3、若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

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

      无向图的深度优先搜索


      第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

      有向图的深度优先搜索

      下面以"有向图"为例,来对深度优先搜索进行演示。


      对上面的图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


      02   广度优先搜索

      广度优先搜索算法(Breadth First Search),又称为"宽度优先搜索"或"横向优先搜索",简称BFS。

      它的思想是:

      1、访问顶点vi;

      2、访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ;

      3、依次从这些邻接点(在步骤②中访问的顶点)出发,访问它们的所有未被访问的邻接点; 依此类推,直到图中所有访问过的顶点的邻接点都被访问;

      换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远,依次访问和v有路径相通且路径长度为1,2...的顶点。

      无向图的广度优先搜索


      第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

      有向图的广度优先搜索


      第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

遍历例程


      实例代码






      关于图的遍历,我们介绍到这,如果有问题,请到后台咨询哦!


  • 友情链接

关注东软睿道公众号了解更多IT行业资讯

添加东小萌微信
获取更多IT学习资源