图（二）.

Presentation on theme: "图（二）."— Presentation transcript:

1 图（二）

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

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

4 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

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

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

7 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

8 深度遍历: 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); }

9 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); }

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

11 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

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

13 广度优先遍历算法 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); }

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

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

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

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