6-4 邻接多重表存储

6-5 图的遍历

遍历定义：从已给的连通图中某一顶点出发，沿着一些边遍访图中所有的顶点，且使每个顶点仅被访问依次，就叫做图的遍历，它是图的基本运算

遍历实质：找每个顶点的邻接点的过程

图的遍历

图中可能存在回路，且图的任一顶点都有可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点

怎样避免重复访问？

解决思路：设置辅助数组visited[n]，用来标记每个被访问过的结点

• 初始状态visited[i]为0
• 顶点i被访问，改visited[i]为1，防止被多次访问

图常用的遍历：

• 深度优先搜索(Depth-First Search)
• 广度优先搜索(Breadth-First Search)

深度优先遍历（DFS）