教学课件 数据结构实用教程(C语言版) 王欣欣.ppt

V1 V2 V3 V4 V5 V6 V7 V8 深度优先有哪些信誉好的足球投注网站结果： V1 → V2 → V4 → V8 → V5 → V3 → V6 → V7 例 A B L M C F D E G H K I J A L M J B F C D E G I K H V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 例 V1 V2 V4 V5 V3 V7 V6 V8 深度遍历：V1? V2 ?V4 ? V8 ?V5 ?V6 ?V3 ?V7 算法6.1 //-----------算法使用全局变量------------ int visited[MAX]; //访问标志数组 Status(*VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 对图G作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; ++v) visited[v] = 0; // 访问标志数组初始化 for (v=0; vG.vexnum; ++v) if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS } 算法6.2 void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G visited[v]=1; VisitFunc (v) ; //访问第v个顶点 for(w=FirstAdjVex(G, v);w=0; w=NextAdjVex(G, v,w)) if(!visited[w]) DFS(G,w) ; //对v的尚未访问的邻接顶点w递归调用DFS } 从上页的图解可见: 1. 深度优先有哪些信誉好的足球投注网站遍历连通图的过程类似于树的先根遍历； 解决的办法是：为每个顶点设立一个 “访问标志 visited[w]”。 2. 如何判别V的邻接点是否被访问？ 2、广度优先有哪些信誉好的足球投注网站 从图中的某个顶点V0出发，并在访问此顶点之后，依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 遍历类似于树的按层次遍历过程 广度优先有哪些信誉好的足球投注网站结果： V1 → V2 → V3 → V4 → V5 → V6 → V7 → V8 V1 V2 V3 V4 V5 V6 V7 V8 对顶点的访问操作 LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在 // 图中“位置” ；否则返回其它信息。 GetVex(G, v); // 返回 v 的值。 PutVex(G, v, value); // 对 v 赋值value。 对邻接点的操作 FirstAdjVex(G, v); // 返回 v 的“第一个邻接点” 。若该顶点 // 在 G 中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); // 返回 v 的(相对于 w 的)“下一个邻接点”。 // 若w是v的最后一个邻接点，则返回“空”。 插入或删除顶点 InsertVex(G, v); //在图G中增添新顶点v。 DeleteVex(G, v); // 删除G中顶点v及其相关的弧。 插入和删除弧 InsertArc(G, v, w); // 在G中增添弧v,w，若G是无向的， // 则还增添对称弧w,v。 DeleteArc(G, v, w); //在G中删除弧v,w，若G是无向的， //则还删除对称弧w,v。 遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每