第七章 图 知识点2：图的存储结构.

Presentation on theme: "第七章 图 知识点2：图的存储结构."— Presentation transcript:

1 第七章 图 知识点2：图的存储结构

2 1、顺序映象：图的结构比较复杂，无法以数据元素在存储区 中的物理位置表示元素之间的关系，即图没有顺序存储
结构，但可以借助数组的数据类型表示元素的关系。 2、链式映象：采用多重链表表示图，用由一个数据域和多个指针域组成的节点表示图中的顶点。 1 2 ^ ^ 4 ^ ^ 例 G1 2 4 1 3 存在问题：节点度数不一致，指针域数目设置困难。因此，实际中也不采用这种建诶构，而是根据具体需要设置结点结构和表结构 ^ 1 2 4 ^ ^ 3 例 1 5 3 2 4 G2

3 定义：设G=(V,{E})是有n1个顶点的图，G的邻接矩 阵A是具有以下性质的n阶方阵：
一、数组表示法 使用邻接矩阵表示顶点间相联关系。 定义：设G=(V,{E})是有n1个顶点的图，G的邻接矩 阵A是具有以下性质的n阶方阵： A[i][j]= 若(vi,vj)或<vi,vj>是E(G)中的边 0 若(vi,vj)或<vi,vj>不是E(G)中的边     例 G1 2 4 1 3      例 1 5 3 2 4 G2

4 数组表示法是用两个数组分别存储数据元素（顶点的
信息）和数据元素之间的关系（边或弧）的信息。 形式描述如下： #define MAX_VERTEX_NUM //最大顶点数设为20 typedef enum{dg,dn,udg,udn} GraphKind; //图的类型 typedef struct ArcCell{ VRType adj; //vrtype是顶点关系类型 InfoType *info; //弧相关指针信息 }ArcCell,AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM]

5 typedef struct { VertexType vexs[Max_Vertex_Num] ; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //顶点数和边数 GraphKind kind; }Mgragh;

6 特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶 点的无向图需存储空间为n(n+1)/2。 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²。 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和。 有向图中， 顶点Vi的出度是A中第i行元素之和。 顶点Vi的入度是A中第i列元素之和。

7 网络的邻接矩阵可定义为： wij 若(vi,vj)或<vi,vj>是E(G)中的边
A[i][j]= wij 若(vi,vj)或<vi,vj>是E(G)中的边 ∞ 若(vi,vj)或<vi,vj>不是E(G)中的边 ∞ 6 1 8 2 4 7 5 3      G1.arcs= 例 A D E B C 7 5 3 1 8 6 4 2 无向网G1 G1.vexs=[A,B,C,D,E] G1.vexnum=5 G1.arcnum= G1.kind=UDN

8 构造过程： Ⅰ顶点和边的数量 G.vexnum=5 G.arcnum=8 Ⅱ顶点信息（数组存储） Ⅲ边的信息（构造前注意数组的初始化） (1,2,5) (1,5,3) (1,3,7) (2,5,8) (3,5,1) (2,4,4) (4,5,6) (3,4,2) 具体算法见P162

9 二、邻接表：为图中每个顶点建立一个单链表，第i个单链表 中的结点表示依附于顶点Vi的边（有向图中vi为弧尾）
表结点：typedef struct ArcNode { // int adjvex; //存放与Vi邻接的点在表头数组中的位置 struct ArcNode *nextarc; //链域，指示下一条边或弧 InfoType *info; }ArcNode; 头结点：typedef struct VNode{ VertexType data; //存放顶点信息 ArcNode *firstarc; //指示第一个邻接点 }VNode,AdjList[Max_Vertex_Num]; } AlGraph adjvex next info data firstarc

10 表： typedef struct { AdjList vertices; int vexnum,arcnum int kind

11 1 2 3 a c d b data firstarc ^ adjvex next 例 G1 b d a c 1 2 3 a c d b data firstarc ^ adjvex next 4 e 例 a e c b d G2

12 无向图中顶点Vi的度为第i个单链表中的结点数 有向图中 顶点Vi的出度为第i个单链表中的结点个数
特点 无向图中顶点Vi的度为第i个单链表中的结点数 有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 1 2 3 a c d b data firstarc ^ adjvex next 例 G1 b d a c

13 弧结点：typedef struct ArcBox{ int tailvex, headvex; //弧尾、弧头在表头数组中位置
三、有向图的十字链表表示法 弧结点：typedef struct ArcBox{ int tailvex, headvex; //弧尾、弧头在表头数组中位置 struct ArcBox *hlink；//指向弧头相同的下一条弧 struct arcbox *tlink; //指向弧尾相同的下一条弧 InfoType *info; }ArcBox; 顶点结点：typedef struct VexNode{ VertexType data; //存与顶点有关信息 ArcBox *firstin; //指向以该顶点为弧头的第一个弧结点 ArcBox *firstout; //指向以该顶点为弧尾的第一个弧结点 }VerNode; tailvex headvex hlink tlink info data firstin firstout

14 图： #define MAX_VERTEX_NUM 20
typedef struct { VerNode xlist[MAX_VERTEX_NUM];//顶点数组 int vernum,arcnum; }OLGraph;

15 例 b d a c a b c d 1 2 3 0 2 0 1 2 3 2 0 3 2 3 1 3 0 ^ ^ ^ ^ ^ ^ ^ ^ 边用顶点位置表示 算法 p165

16 typedef emun {unvisited,visited} VisitIf; typedef struct EBox{
四、无向图的邻接多重表表示法 边结点： typedef emun {unvisited,visited} VisitIf; typedef struct EBox{ VisitIf mark; //标志域—访问标志 int ivex, jvex; //该边依附的两个顶点在表头数组中位置 struct EBox *ilink, *jlink; //分别指向依附于ivex和jvex的下一条边 InfoType *info; }EBox; mark ivex ilink jvex jlink info

17 顶点结点： typedef struct VexBox{ VertexType data; //存与顶点有关的信息 EBox *firstedge; //指向第一条依附于该顶点的边 }VerBox; data firstedge

18 #define MAX_VERTEX_NUM 20
typedef struct { VerBox adjmulist MAX_VERTEX_NUM]; int vernum,edgenum; }AMLGraph; 例 a e c b d 返回 1 2 3 a c d b 4 e ^ ^ ^ ^ ^

19 知识点小结 本知识点主要讲解图的四种不同的存储结构——邻接矩阵、邻接表、邻接多重表和十字链表， 讲解不同的存储特点、描述方法，重点掌握最常用的存储方式邻接矩阵和邻接表。