7.2图的存储结构-邻接多重表 7.3图的遍历(1) 邻接多重表一无向图 。图的遗历 ∥顶，点结点 顶点之间的邻接关系m:n typedef struct Vex Boxf VertexType data; 引入访问标志数组visited0.n-1],防止顶点多 EBox *firstedge; 次被访问 VexBox: 。图的遗历种类 川邻接多重表 。深度优先遍历：→树的先序遭历 typedef structf 从莱顶点出发，访问该顶点，然后依次从的来被访 Vex Box adjmulist[MAX_VERTEX_NUM]; 问的邮接点出发派度优先通历图，直至图中所有和有 int vexnum,edgenum; AMLGraph; 回 路径相通的顶燕虾被访问到： 38106 ☑图 7.3图的遍历(2) 7.3图的遍历(3) ·图的速历种类 ·广度优先遵历：)树的层次遭历 从某顶旅”出发，访问被顶点，然后依次访问v的所有 来曾访问过的你接点，再分别从这些邻接点出发依次 访问它们的怀接点，并使“先放拉问的顶点的邻接点 先于“后被过问的顶点的年接点”放黄问，直至用中所 有已被访问的项成的饰接点都被访问到： 生成树 。若困中还存在尚来访问过的顶点，则另选图中一个来 遍历序列 曹被访问的项点作起地点，继续重复上述过程 深度优先旋素(DS) 广度优先校素(BFS) 39/106 回 V V2 Vi VsVs VV V7 0H06 ViV2VaViVsVaV,Vs 图 基于ADT Graphe的DFS算法（算法7.4和7.5） 73图的遍4) Boolean visited[MAX VERTEX NUMI: void DFSTraverse(Graph G,Status (*Visit)(Graph G.int v)) DFSTraverse(G) for (v-0;v<G.vexnum;++v)visitedlv]=FALSE; ,基于ADT Graph for (v-0;v <G.vexnum;++v) if (!visited v) ·基于某种在储结构：邻接矩阵/邻接表/十字链 DFS(G,v,Visit); 表/邻接多重表 ■BFSTraverse(G) void DFS(Graph G,int v,Status (*Visit)(Graph G,int v)) ,基于ADT Graph visitedlv]=TRUE;Visit(G,v); ,基于某种存储结构：邻接矩阵/邻接表/十字链 for (w-FirstAdjVex(G,v);w;w-NextAdjVex(G,v,w)) 表/邻接多重表 if (visitedwl) DFS(G.w.Visit): 41/106 图 42/10637/106 7.2 图的存储结构-邻接多重表 „ 邻接多重表—无向图 // 顶点结点 typedef struct VexBox{ VertexType data; EBox *firstedge; }VexBox; //邻接多重表 typedef struct{ VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; }AMLGraph; 38/106 7.3 图的遍历(1) „ 图的遍历 顶点之间的邻接关系m : n 引入访问标志数组visited[0..n-1]，防止顶点多 次被访问 „ 图的遍历种类 „ 深度优先遍历：Æ 树的先序遍历 从某顶点v 出发，访问该顶点，然后依次从v 的未被访 问的邻接点出发深度优先遍历图，直至图中所有和v 有 路径相通的顶点都被访问到； 39/106 7.3 图的遍历(2) „ 图的遍历种类 „ 广度优先遍历：Æ 树的层次遍历 从某顶点v 出发，访问该顶点，然后依次访问v 的所有 未曾访问过的邻接点，再分别从这些邻接点出发依次 访问它们的邻接点，并使“先被访问的顶点的邻接点” 先于“后被访问的顶点的邻接点” 被访问，直至图中所 有已被访问的顶点的邻接点都被访问到； „ 若图中还存在尚未访问过的顶点，则另选图中一个未 曾被访问的顶点作起始点，继续重复上述过程 40/106 7.3 图的遍历(3) V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 V5 V6 V7 V8 深度优先搜索(DFS) V1 V1 V2 V2 V4 V4 V8 V5 V8 V5 V3 V3 V6 V6 V7 V7 生成树 遍历序列 广度优先搜索(BFS) V1 V1 V2 V2 V3 V3 V4 V4 V5 V5 V6 V6 V7 V7 V8 V8 最短 路径! 41/106 7.3 图的遍历(4) „ DFSTraverse(G) „ 基于ADT Graph „ 基于某种存储结构：邻接矩阵/邻接表/十字链 表/邻接多重表 „ BFSTraverse(G) „ 基于ADT Graph „ 基于某种存储结构：邻接矩阵/邻接表/十字链 表/邻接多重表 42/106 基于ADT Graph的DFS算法(算法7.4和7.5) Boolean visited[MAX_VERTEX_NUM]; void DFSTraverse(Graph G, Status ( *Visit ) (Graph G, 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, Visit); } void DFS(Graph G, int v, Status ( *Visit ) (Graph G, int v) ) { visited[v] = TRUE; Visit(G, v); for ( w = FirstAdjVex(G, v); w; w = NextAdjVex(G, v, w) ) if ( !visited[w] ) DFS(G, w, Visit); }