图（二）

教学目标 熟练掌握图的深度优先遍历算法； 熟练掌握图的广度优先遍历算法。 2/14

图的遍历 深度优先遍历(DFS) 方法：从图的某一顶点V1出发，访问此顶点；然后依次从V1的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V1相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V2 V4  V8 V5 V3 V6 V7

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

V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V2 V4  V8 V3 V6 V7 V5

深度优先遍历算法 V1 V2 V4 V5 V3 V7 V6 V8 例 递归算法 深度遍历：V1 V3  V7  V6  V2  vexdata firstedge 7 8 ^ adjvex next 5 6

V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V3  V7  V6  V2  V4  V8  V5 1 vexdata firstedge 7 8 ^ adjvex next 5 6

深度遍历: int visited[MaxVerNum]; void dfstraverse(ALGraph G) { int v; for(v=0; v<G.n; v++) visited[v] = 0; if(!visited[v]) dfs(G, v); }

void dfs(ALGraph G, int v) { EdgeNode *p; int w; visit(v); //访问第v个顶点 visited[v] = 1; for(p=G.Adjlist[v].firstedge; p; p=p->next) w = p->adjvex; if(!visited[w]) dfs(G,w); }

广度优先遍历(BFS) 方法：从图的某一顶点V1出发，访问此顶点后，依次访问V1的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止 V1 V2 V4 V5 V3 V7 V6 V8 例 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8

V1 V2 V4 V5 V3 V7 V6 V8 例 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8 例 V1 V2 V4 V5 V3 V7 V6 V8 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8

V1 V2 V4 V5 V3 V7 V6 V8 例 广度遍历：V1 V2 V3  V4 V6 V7 V8 V5

广度优先遍历算法 void bfs(ALGraph G, int v) { EdgeNode *p; int u,v,w; Q = Init_seqQueue(); visit(v); visited[v] = 1; In_SeqQueue(Q,v); while(!(Empy_seqQueue(Q))) { out_sequeue(Q,&u); for(p=G.adjlist[u].firstedge; p ; p->next) { w = p->adjvex; if(!visited[w]) visit(w); visited[w] = 1; In_SeqQueue(Q,w); }

1 2 3 4 vexdata firstedge 5 ^ adjvex next 例 1 4 2 3 5 0 1 2 3 4 5 1 f r 遍历序列：1 0 1 2 3 4 5 4 f r 遍历序列：1 4 0 1 2 3 4 5 4 3 f r 遍历序列：1 4 3

1 2 3 4 vexdata firstarc 5 ^ adjvex next 例 1 4 2 3 5 0 1 2 3 4 5 4 3 2 f r 遍历序列：1 4 3 2 0 1 2 3 4 5 3 2 f r 遍历序列：1 4 3 2 0 1 2 3 4 5 3 2 5 f r 遍历序列：1 4 3 2 5

1 2 3 4 vexdata firstarc 5 ^ adjvex next 例 1 4 2 3 5 0 1 2 3 4 5 2 5 f r 遍历序列：1 4 3 2 5 0 1 2 3 4 5 5 f r 遍历序列：1 4 3 2 5 0 1 2 3 4 5 f r 遍历序列：1 4 3 2 5

作业 1.设计图的深度优先遍历算法（用邻接表作为存储结构）。 2. 设计图的广度优先遍历算法（用邻接矩阵作为存储结构）。