★无向图的邻接多重表表示法 边结点: typedef struct node int mark;∥标志域 int ivex,jvex;∥该边依附的两个顶点在表头数组中位置 struct node* ilink,*link;∥分别指向依附于ivex和jvex的下一条边 JJD mark ivex ilink jex jlink 顶点结点: typedef struct dnode int data;∥存与顶点有关的信息 struct node* firstedge;∥指向第一条依附于该顶点的边 JDD DDga[M];∥/ga[0]不用 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
例 4 12345 abcde 2 4 2
例 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出发,访问此顶点:然后依 次从V的未被访问的邻接点出发,深度优先遍历图 直至图中所有和V相通的顶点都被访问到;若此时图 中尚有顶点未被访问.则另选图中一个未被访冋的顶 点作起点。重复上述过程,直至图中所有顶点都被访 问为止 例 深度遍历:V1→V2→V4→Ⅴ8→V5→V3→V6→V7
§6.3 图的遍历 深度优先遍历(DFS) ❖方法：从图的某一顶点V0出发，访问此顶点；然后依 次从V0的未被访问的邻接点出发，深度优先遍历图， 直至图中所有和V0相通的顶点都被访问到；若此时图 中尚有顶点未被访问，则另选图中一个未被访问的顶 点作起点，重复上述过程，直至图中所有顶点都被访 问为止 V1 V2 V4 V5 V3 V6 V7 V8 例 深度遍历：V1V2 V4 V8 V5 V3 V6 V7
例 深度遍历:Ⅵ1→V2→V4→V8→V5→V6→V3→V7 例 V4)(8 深度遍历:V1→V2→Ⅵ4→V8→V5→V6→V3→V7
V1 V2 V4 V5 V3 V6 V7 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 深度遍历：V1V2 V4 V8 V5 V6 V3 V7 深度遍历：V1V2 V4 V8 V5 V6 V3 V7
例 深度遍历:V1→V2→V4→V8→V3→V6→V7→V5
V1 V2 V4 V5 V3 V6 V7 V8 例 深度遍历：V1V2 V4 V8 V3 V6 V7 V5