数据结构重读 – 图的遍历(概念)

图的遍历:从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。

图比树复杂,为了避免同一顶点被访问多次,可以设置一个辅助数组,初始值置为False或者0。当访问到后,设置值为真或被访问的次序ID。

图遍历主要有两种:深度优先搜索、广度优先搜索。

深度优先遍历

是树的先根遍历的推广。

从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v相连通的路径都被访问到。然后再另选一个未被访问的结点做为起始点。

代码如下:

当用邻接矩阵(二维数组表示时),查找顶点邻接点的复杂度为O(n^2)。

用邻接表时,实践复杂度为O(n+e)。

广度优先遍历

类似树的层次遍历。

使得“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直到图中所有已被访问的顶点的邻接点都被访问到。此时再选取图中另一个未曾被访问的顶点做为起始点。

实际是依次访问和v有路径、相连通且路径长度为1,2,3。。。的顶点。

和层次遍历一样,也要借助队列,代码如下:

 

Leave a Reply

Your email address will not be published.