数据结构第7章图.ppt
1,第七章 图,7.1 图的类型定义,7.2 图的存储结构,7.3 图的遍历,7.4 最小生成树,7.5 有向无环图及其应用,7.6 最短路径,2,其中：V=ei|eiElemSet,i=1,2,n R=VR VR=|v,wV 且 P(v,w)谓词 P(v,w)定义了 之间关系的意义或信息。,7.1 图的类型定义,图 是由一个顶点集 V 和一个关系集 R构成的数据结构。,Graph=(V,R),3,7.2 图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、无向图的邻接多重表存储表示,4,一、邻接矩阵,在存储图的结构时，至少要保存两类信息：顶点的数据顶点之间的关系数组表示法：使用两个数组，其中一个用来存储顶点的数据，另一个用来存储顶点之间的关系(弧)，表示弧的矩阵被称为邻接矩阵（二维数组）。具有n个顶点的图G的邻接矩阵是具有如下性质的n阶矩阵：,5,6,无向图邻接矩阵表示法特点：无向图邻接矩阵是对称矩阵，同一条边表示了两次,无向图的总边数为非0元素个数的一半；顶点v的度:等于二维数组对应行（或列）中1的个数；判断两顶点v、u是否为邻接点:只需判断二维数组对应分量是否为1；顶点不变，在图中增加、删除边:只需对二维数组对应分量赋值1或清0；设图的顶点数为 n,存储图用一维数组,数组元素有m（m=n)个,则G占用存储空间：m+n2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；,7,无向图的邻接矩阵为对称矩阵。,8,有向图邻接矩阵表示法特点：有向图邻接矩阵不一定是对称矩阵；有向图的弧数是矩阵中1的个数。顶点v的出度：等于二维数组对应行中1的个数；顶点v的入度：等于二维数组对应列中1的个数；有向图的总弧数为非0元素个数。网的邻接矩阵:,9,图的数组存储表示#define INFINITY INT_MAX/最大值#define MAX_VERTEX_NUM 20/最大顶点个数typedef enum DG,DN,AG,AN GraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCell/存储弧/边的信息，即邻接矩阵 VRType adj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,10,图的数组存储表示typedef struct/存储数据元素信息 VertexType vexsMAX_VERTEX_NUM;/存储数据元素信息，即顶点向量 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧(边)数 GraphKind kind;/图的种类标志 MGraph;,11,邻接矩阵的数据类型定义#define MaxV 100/定义最大顶点数typedef structint vexesMaxV;/顶点表 int edgesMaxVMaxV;/邻接矩阵 int n,e;/顶点数n和边数eMGraph;,12,二、邻接表,邻接表是图（包括有向图和无向图）的链式存储结构。对于图中的每个顶点vi，把所有邻接于vi的各个顶点链成一个单链表，称为边链表。无向图中顶点vi的边链表中每个结点都对应一个与vi关联的边；有向图中顶点vi的边链表中每个结点都对应一个以vi为始顶点的弧，因此称为出边表。,13,为每个顶点vi的边链表建立一个头结点，存储在一维数组中(即顶点表)，以便随机访问任一顶点的边链表。因此，在邻接表中有两种结点：链表结点 和 顶点结点邻接表是一种顺序+链式存储结构。用顺序表存放顶点，为每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边或以该顶点为尾的弧。,14,顶点数据结点（数组元素）由两个域组成：数据域（data）:存储顶点名称或其他信息。链域（firstarc）:指向链表中第一个结点(边)。边链表的每个结点由3个域组成：邻接点域（adjvex）：指示与顶点 vi 邻接的顶点在图中的位置。链域（nextarc）:指示下一条边或弧的结点。数据域（info）:存储和边或弧相关的信息。,15,图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode/边链表结点int adjvex;/该弧所指向的顶点的位置struct ArcNode*nextarc;/指向下一条弧的指针InfoType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode/头结点VertexType data;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;,16,图的邻接表存储表示 typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志 ALGraph;,17,无向图的邻接表示例,注意：没有画出链表结点的info域。,18,无向图的邻接表的特点边链表中结点总数是图中边数的2倍；顶点v的度：等于v对应链表的长度判定两顶点v，u是否邻接：要看v对应链表中有无对应的结点；在图中增减边：要在两个单链表插入、删除结点；设存储顶点的一维数组大小为m(m图的顶点数n),图的边数为e，图占用存储空间为：m+2*e。图占用存储空间与图的顶点数、边数均有关；适用于边稀疏的图。,19,有向图的邻接表：边链表中结点总数等于图中弧数；每个边链表的结点数是相应顶点的出度；求入度需遍历边表中所有结点，或者建立逆邻接表。逆邻接表是为图中每个顶点建立一个入边表。,20,有向图的邻接表,0,1,2,3,4,5,data,firstarc,vexnum=6,arcnum=7,21,有向图的逆邻接表,0,1,2,3,4,5,data,firstarc,vexnum=6,arcnum=7,单链表中的结点表示以该顶点为头的弧,22,网的邻接表的数据类型定义：#define MaxV 100typedef struct node/边链表的结点类型int adjvex;/该弧所指向的顶点的位置float weight;/边的权值struct node*next;/指向下一条弧的指针Enode;typedef struct/表头结点类型 VertexType data;/顶点信息 Enode*firste;/指向第一条依附该顶点的弧 Vnode;,23,网的邻接表的数据类型定义：typedef structVnode adjlistMaxV;/邻接表int n,e;/顶点数和边数ALGraph;,24,三、十字链表(有向图),十字链表是有向图的另一种链式存储结构。将有向图的邻接表和逆邻接表结合起来的结构。在十字链表中有两种结点：弧结点：存储每一条弧的信息，用链表链接在一起。顶点结点：存储每一个顶点的信息，使用一维数组来存储。,顶点结点结构:,弧结点结构:,25,typedef struct ArcBox/弧的结构表示 int tailvex,headvex;/指示该弧的头和尾的位置 InfoType*info;struct ArcBox*hlink,*tlink;/指向弧头链表和弧尾链表的下一个结点 VexNode;,typedef struct VexNode/顶点的结构表示 VertexType data;ArcBox*firstin,*firstout;/指向以该顶点为头和尾/的两个链表 VexNode;,26,typedef struct/图结构 VexNode xlist20;/顶点结点向量 int vexnum,arcnum;/顶点数和弧数 OLGraph;,27,十字链表中既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。,28,四、邻接多重表(无向图),邻接多重表是无向图的另一种链式表示结构。和十字链表类似。邻接多重表中，每一条边用一个结点表示。在邻接多重表中有两种结点：边结点：存储每一条边的信息，用链表链接在一起。顶点结点：存储每一个顶点的信息，使用一维数组来存储。,顶点结点结构:,边结点结构:,29,typedef struct VexBox/顶点结点 VertexType data;EBox*firstedge;/指向第一条依附该顶点的边 VexBox;,typedef struct Ebox/边结点 VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox*ilink,*jlink;/指向依附于ivex,jvex的下一条边结点 InfoType*info;EBox;,30,typedef struct/图结构 VexBox adjmulist20;int vexnum,edgenum;AMLGraph;/邻接多重表,31,32,练习1.给出下图所示无向图的邻接矩阵存储结构,33,练习1.,1 2 3 4 5 6 7 8 9,1 2 3 4 5 6 7 8 9,34,练习2.给出下图所示有向网的邻接矩阵存储结构,35,练习2.,1 2 3 4 5 6,1 2 3 4 5 6,36,练习3.给出下图所示带权无向图的邻接表存储结构,37,练习3.,
