第七章 图1图的定义2存储结构.ppt

优点： 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 缺点： n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。 优点： 空间效率高；容易寻找顶点的邻接点。 缺点： 判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。 二.邻接表 1 . 无向图的邻接表 表头结点 data firstarc adjvex nextarc 边(弧)结点 data：顶点信息 firstarc：指向关联该顶点的第一条边(弧)链表 adjvex：边(弧)的另一顶点的在数组中的位置 nextarc：指向下一条边(弧)结点的指针 0 1 2 3 4 m-1 V1 V2 V3 V4 V5 1 3 4 2 2 1 1 0 0 2 3 4 Info Info：该弧的相关信息的指针 二.邻接表 #define MAX_VERTEX_NUM 20 typedef struct ArcNode{ //边(弧)结点的类型定义 int adjvex; //该弧所指向顶点的位置 struct ArcNode *nextarc; InfoType *info; //该弧相关信息的指针 }ArcNode; typedef struct VNode { //表头结点的类型定义 VertexType data; //顶点信息 ArcNode * firstarc; }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; //顶点数组 int vexnum, arcnum; //图的当前顶点数和弧数 int kind; //图的种类标志 }ALGraph; 设G是ALGraph 类型的变量，用于存储无向图G，该图有n个顶点，e条边。G的图示如下： V5 V1 V2 V4 V3 无向图G G.vertices G.vexnum G.arcnum G.kind 0 1 2 4 m-1 V1 V2 V3 V4 V5 5 6 UDG 1 3 4 2 2 1 1 0 0 2 3 data firstarc adjvex nextarc 4 V5 V1 V2 V4 V3 1）在G邻接表中，同一条边对应两个结点； 2）顶点v的度：等于v对应线性链表的长度； 3）判定两顶点v ，u是否邻接：要看v对应线性链表中有无对 应的结点； 4）在G中增减边：要在两个单链表插入、删除结点； 5）设存储顶点的一维数组大小为m, 图的边数为e，G占用存 储空间为：m+2*e。G占用存储空间与G的顶点数、边数均 有关；适用于边稀疏的图； 0 1 2 3 4 m-1 V1 V2 V3 V4 V5 1 3 4 2 2 1 1 0 0 2 3 4 说明 二.邻接表 2 . 有向图的邻接表 顶点：用一维数组存储 （按编号顺序） 以同一顶点为起点的弧： 用线性链表存储 D.vertices D.vexnum D.arcnu D.kind V1 V2 V3 V4 4 4 DG 1 2 3 0 V1 V2 V3 V4 0 1 2 3 二.邻接表 3 . 有向图的逆邻接表 顶点：用一维数组存储 （按编号顺序） 以同一顶点为终点的弧： 用线性链表存储表 D.vertices D.vexnum D.arcnu D.kind V1 V2 V3 V4 4 4 DG 0 0 2 3 V1 V2 V3 V4 0 1 2 3 二.邻接表 例 b d a c a b c d 1 2 3 4 1 3 1 2 3 4 3 1 4 3 4 2 4 1 ^ ^ ^ ^ ^ ^ ^ ^ 自学：十字链表表示法 164页 ab ac ca cd da db dc 三.有向图邻接表的构造 A B L M C F D E G H J K I 13,13 ABCDEFGHIGKLM AB AC AF AL BM DE GH GI GK HK JL JM LM 例 .tx