图的遍历-深度优先遍历
图的遍历通常有2种:深度优先遍历和广度优先遍历。
深度优先遍历(DepthFirstSearch):也称为深度优先搜索,简称DFS。
从A为开始点,顺序为A、B、C、D、E、F、G、H、I、
wqewq
约定右手原则:在没有碰到重复顶点的情况下,分叉路口始终是向右手边走,每路过一个顶点就做一个记号。
(深度优先遍历其实就是递归的过程)
(整个遍历过程好像是一棵树的前序遍历)
当走到每个点都是先选最右那个点,如果最右的点遍历过,则选择从右数第二个点,依次推,当遇到该点的右手原则的点都遍历过时,往前退一个点重复这个过程,直到遍历结束。退回到原始起点。