大连理工大学：《数据结构》课程教学课件（PPT讲稿）第六章 图

★无向图的邻接多重表表示法 边结点： typedef struct node {int mark,l∥标志域 int ivex,.jvex,∥该边依附的两个顶点在表头数组中位置 struct node*ilink,*jlink,/分别指向依附于ivex和jvex的下一条边 JD; mark ivex ilink Jvex ilink 顶点结点： typedef struct dnode {int data,∥存与顶点有关的信息 struct node*firstedge;/指向第一条依附于该顶点的边 DD; DD ga[M;/gaO]不用 data firstedge

无向图的邻接多重表表示法 顶点结点： typedef struct dnode { int data; //存与顶点有关的信息 struct node *firstedge; //指向第一条依附于该顶点的边 }DD; DD ga[M]; //ga[0]不用 data firstedge 边结点： typedef struct node { int mark; //标志域 int ivex, jvex; //该边依附的两个顶点在表头数组中位置 struct node *ilink, *jlink; //分别指向依附于ivex和jvex的下一条边 }JD; mark ivex ilink jvex jlink

例 e a d 2 3^ 5

例 a e c b d 1 2 3 4 a c d b 5 e 1 2 1 4 3 2 3 4 5 2 3 5 ^ ^ ^ ^ ^

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

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

例 (V3 深度遍历：V1三V2三V4→V8=V5=V6=V3=V7 例 W (W6 V3 V4 Vi 深度遍历：V1→V2三V4三V8三→V5三V6=V3三V7

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

例 (VI V2 (V3 4 W⑧ 深度遍历：V1→V2→V4→V8→V3=V6→V7=V5

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