【数据结构】图的遍历概述关键问题1. 深度优先遍历 （DFS：Depth First Search）2. 广度优先遍历 （BFS：Broad First Search ；FIFO: First In First Out）

图的遍历是从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。
是一种抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。

关键问题

① 在图中，如何选取遍历的起始顶点？

在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。
为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。
解决方案：从编号小的顶点开始 。

② 从某个起点始可能到达不了所有其它顶点，怎么办？

从某顶点出发遍历图的算法。
解决方案：多次调用从某顶点出发遍历图的算法。

③ 因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环?

解决方案：附设访问标志数组visited[n] 。

④ 在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？

解决方案：深度优先遍历和广度优先遍历。

1. 深度优先遍历 （DFS：Depth First Search）

基本思想 ：

⑴ 访问顶点v；
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

深度优先搜索是带回溯的，许多问题的解决都是通过深度优先搜索方法解决的。—>利用栈实现

2. 广度优先遍历 （BFS：Broad First Search ；FIFO: First In First Out）

基本思想：

⑴ 访问顶点v；
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

最后

以上就是畅快煎饼为你收集整理的【数据结构】图的遍历概述关键问题1. 深度优先遍历 （DFS：Depth First Search）2. 广度优先遍历 （BFS：Broad First Search ；FIFO: First In First Out）的全部内容，希望文章能够帮你解决【数据结构】图的遍历概述关键问题1. 深度优先遍历 （DFS：Depth First Search）2. 广度优先遍历 （BFS：Broad First Search ；FIFO: First In First Out）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。