数据结构与算法_图的遍历

图结构遍历的方法：深度优先，广度优先

深度优先遍历是按照深度优先搜索（Depth First Search,DFS）的方式对图进行遍历。

深度优先搜索是最常见得图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退到刚刚访问的节点，似不撞南墙不回头，不到黄河不死心。

    深度优先遍历秘籍：

    后被访问的顶点，其邻接点先被访问。

    根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。由于递归本身是使用栈实现的，因此使用递归方法更方便。

    算法步骤：

    1.初始化图中所有顶点未被访问。

    2.从图中的某个顶点v出发，访问v并标记为被访问。

    3.依次检查v的所有邻接点w,如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复2-3步）。

广度优先遍历是按照广度优先搜索（Breadth First Search ,BFS）的方式对图进行遍历，又称宽度优先 。

广度优先搜索是最常见的图搜索方法之一。广度优先搜索是从某一个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过邻接点出发，...，似水中涟漪，似声音传播，一层层得传播开来。

    广度优先遍历秘籍 ：

    先被访问的顶点，其邻接点先被访问。

    根据广度优先遍历秘籍，先来先服务，可以借助于队列来实现。每个节点访问一次且只访问一次，因此可以设置一个辅助数组：

    visited[i] = false,表示第i个顶点未访问；

    visited[i] = true,表示第i个顶点已经访问。

    算法步骤：

    1.初始化图中所有顶点未被访问，初始化一个空队列。

    2.从图中的某个顶点v出发，访问v并标记已经访问，将v入队；

    3.如果队列非空，则继续执行，否则算法结束；

    4.队头元素v出队，依次访问v的所有未被访问邻接点，标记已访问并入队。转向步骤3；