《数据结构教学课件：第七讲2图》由会员分享，可在线阅读，更多相关《数据结构教学课件：第七讲2图（13页珍藏版）》请在金锄头文库上搜索。
1、n7.2 图的存储结构u多重链表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3u邻接矩阵表示顶点间相联关系的矩阵F定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G2F特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网络的邻接矩阵可定义为：例1452375318642u邻接
2、表F实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）typedef struct node int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next; /链域，指示下一条边或弧JD;adjvex next表头结点：typedef struct tnode int vexdata; /存放顶点信息 struct node *firstarc; /指示第一个邻接点TD;TD gaM; /ga0不用vexdata firstarc例G1bdac例aecbdG21234acdbvexdata
3、firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 3F特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex nextn7.3 图的遍历u深度优先遍历(DFS)F方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发
4、，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5u广度优先遍历(BFS)F方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5
