深度优先搜索(Depth First Search,DFS)
DFS遍历类似于树的先序遍历,是树的先序遍历的推广。
DFS的过程如下:
- 从图中某个定点v出发,访问v。
- 找出刚访问过的顶点的第一个未被访问的邻接点,访问该顶点。以该顶点为新顶点,重复此不走,直到刚访问过的顶点没有未被访问的邻接点为止。
- 返回前一个访问过的且仍有未被访问的邻接点的顶点,找出该顶点的下一个未被访问的邻接点,访问该顶点。
- 重复步骤(2)和(3),直到图中所有顶点都被访问过,搜索结束。
实现:依靠栈,一维数组和图的邻接矩阵存储方式
广度优先搜索(Breadth First Search,BFS)
BFS遍历类似于树的安层次遍历的过程。
BFS过程如下:
- 从图中某个顶点v出发,访问v。
- 依次访问v的各个未增访问过的邻接点。
- 分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。
- 重复不走(3)直到图中所有已被访问的顶点的邻接点都被访问到。
实现:依靠队列和一维数组来实现