12b243db9757bd69797231efb84bc3a3
数据结构与算法——图的遍历

1 引言

  遍历是指从某个节点出发,按照一定的的搜索路线,依次访问对数据结构中的全部节点,且每个节点仅访问一次。
  在二叉树基础中,介绍了对于树的遍历。树的遍历是指从根节点出发,按照一定的访问规则,依次访问树的每个节点信息。树的遍历过程,根据访问规则的不同主要分为四种遍历方式:
  (1)先序遍历
  (2)中序遍历
  (3)后序遍历
  (4)层次遍历
  类似的,图的遍历是指,从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列
  图的遍历过程中,根据搜索方法的不同,又可以划分为两种搜索策略:
  (1)深度优先搜索(DFS,Depth First Search)
  (2)广度优先搜索(BFS,Breadth First Search)

2 深度优先搜索

2.1 算法思想

  深度优先搜索思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

2.2 算法特点

  深度优先搜索是一个递归的过程。首先,选定一个出发点后进行遍历,如果有邻接的未被访问过的节点则继续前进。若不能继续前进,则回退一步再前进,若回退一步仍然不能前进,则连续回退至可以前进的位置为止。重复此过程,直到所有与选定点相通的所有顶点都被遍历。
  深度优先搜索是递归过程,带有回退操作,因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时,需要进行出栈操作,将当前位置回退至出栈元素位置。

2.3 图解过程

2.3.1 无向图深度优先搜索

以图2.3.1.1中所示无向图说明深度优先搜索遍历过程。
图2.3.1.1

图2.3.1.1

(1)首先选取顶点A为起始点,输出A顶点信息,且将A入栈,并标记A为已访问顶点。

(2)A的邻接顶点有C、D、F,从中任意选取一个顶点前进。这里我们选取C顶点为前进位置顶点。输出C顶点信息,将C入栈,并标记C为已访问顶点。当前位置指向顶点C。

(3)顶点C的邻接顶点有A、D和B,此时A已经标记为已访问顶点,因此不能继续访问。从B或者D中选取一个顶点前进,这里我们选取B顶点为前进位置顶点。输出B顶点信息,将B入栈,标记B顶点为已访问顶点。当前位置指向顶点B。

(4)顶点B的邻接顶点只有C、E,C已被标记,不能继续访问,因此选取E为前进位置顶点,输出E顶点信息,将E入栈,标记E顶点,当前位置指向E。

(5)顶点E的邻接顶点均已被标记,此时无法继续前进,则需要进行回退。将当前位置回退至顶点B,回退的同时将E出栈。

(6)顶点B的邻接顶点也均被标记,需要继续回退,当前位置回退至C,回退同时将B出栈。

(7)顶点C可以前进的顶点位置为D,则输出D顶点信息,将D入栈,并标记D顶点。当前位置指向顶点D。

(8)顶点D没有前进的顶点位置,因此需要回退操作。将当前位置回退至顶点C,回退同时将D出栈。

(9)顶点C没有前进的顶点位置,继续回退,将当前位置回退至顶点A,回退同时将C出栈。

(10)顶点A前进的顶点位置为F,输出F顶点信息,将F入栈,并标记F。将当前位置指向顶点F。

(11)顶点F的前进顶点位置为G,输出G顶点信息,将G入栈,并标记G。将当前位置指向顶点G。

(12)顶点G没有前进顶点位置,回退至F。当前位置指向F,回退同时将G出栈。

(13)顶点F没有前进顶点位置,回退至A,当前位置指向A,回退同时将F出栈。

(14)顶点A没有前进顶点位置,继续回退,栈为空,则以A为起始的遍历结束。若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程。直至所有顶点均被访问。

(15)采用深度优先搜索遍历顺序为A->C->B->E->D->F->G。

2.3.2 有向图深度优先搜索

以图2.3.2.1中所示有向图说明深度优先搜索遍历过程。
图2.3.2.1 有向图

图2.3.2.1 有向图

(1)以顶点A为起始点,输出A,将A入栈,并标记A。当前位置指向A。

(2)以A为尾的边只有1条,且边的头为顶点B,则前进位置为顶点B,输出B,将B入栈,标记B。当前位置指向B。

(3)顶点B可以前进的位置有C与F,选取F为前进位置,输出F,将F入栈,并标记F。当前位置指向F。

(4)顶点F的前进位置为G,输出G,将G入栈,并标记G。当前位置指向G。

(5)顶点G没有可以前进的位置,则回退至F,将F出栈。当前位置指向F。

(6)顶点F没有可以前进的位置,继续回退至B,将F出栈。当前位置指向B。

(7)顶点B可以前进位置为C和E,选取E,输出E,将E入栈,并标记E。当前位置指向E。

(8)顶点E的前进位置为D,输出D,将D入栈,并标记D。当前位置指向D。

(9)顶点D的前进位置为C,输出C,将C入栈,并标记C。当前位置指向C。

(10)顶点C没有前进位置,进行回退至D,回退同时将C出栈。

(11)继续执行此过程,直至栈为空,以A为起始点的遍历过程结束。若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程。直至所有顶点均被访问。

2.4 代码实现

top Created with Sketch.