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