深度优先遍历算法

深度优先搜索类似于树的先序遍历。

其基本思想是：

• 首先访问起始顶点v，然后由v出发，访问与v 邻接且未被访问的任一顶点w1，再访问与w1 邻接且未被访问的任一顶点W2……重复上述操作。
• 当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

从顶点a 出发，进行深度优先遍历，可以得到的一种顶点序列为：a e d f c b

2、广度优先遍历算法

广度优先搜索类似于二叉树的层序遍历算法。

其基本思想是：

• 首先访问起始顶点v，接着由ν出发，依次访问v 的各个未访问过的邻接顶点W1，W2，…，Wi，然后依次访问W1，W2，…，Wi的所有未被访问过的邻接顶点；
• 再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中的所有顶点都被访问过为止。
• 若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。