图的遍历的定义以及深度优先搜索和广度优先搜索（一）

图的遍历

定义

图的遍历是从图中某一顶点出发对图中每个顶点访问且仅访问一次的过程。图的遍历算法是求解图的连通性问题拓扑排序和求关键路径等算法的基础。

图的遍历与树的遍历不同在于树中不存在回路沿着分支同一个顶点不可能被访问多次。而在图中却存在回路，所以同一个顶点有可能被多次访问。

为了避免这种现象发生，在图的遍历过程中，必须设置能判别该顶点是否已被访问的标志一般设置一个数组 visited [0 ... n-1]其初值均为'假’,一旦访问了顶点 v 便将 visited [vi] 置'真’。

• 两种遍历方式:深度优先搜索 广度优先搜索

深度优先搜索

• 深度优先搜索类似树的先根序遍历

设图是邻接表的方式存储，与其他邻接表不同的是头顶点中有一个被访问标志位，其初值为“假”。深度优先搜索的过程:在图中任选一个顶点作为出发顶点 V0，访问 V0 后，依次从 V0 的没被访问过的邻接点出发进行深度优先搜索。直到与 V0 所连通的所有顶点均被访问。如果，此时图中还有顶点尚未访问，则从剩余的顶点中再任选一个顶点作为出发顶点 V0，重复上述过程，直到图中全部顶点均被访问为止。如下图遍历序列为(v1，v2，v4，v8，v5，v3，v6，v7)

这是要遍历的图：

这是邻接表

• 深度优先搜索的算法设计与分析（递归）

Boolean visited[MAX];(访问标志数组)

Status(*VisitFunc)(int v);(函数变量)

Void DFSTraverse(Graph G, Status(*visit)(int v)) { (深度遍历)

for (v = 0;v<G.vexnum;++v). visited[v] = FALSE;(初始假值)

for (v = 0;v <G.VEXNUM; ++v)

if(!visited[v]) DFS(G,v);(对尚没访问的顶点调用 DFS)

}

Void DFS(Graph G,int v){(从第 v 个顶点出发递归深度优先)

visited[v] =TRUE;

VisitFunc(v);(访问第 v 个顶点)

for(w =FirstAdjVex(G,V);W>=0;w =NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);

}

• 算法过程图（递归）