@特点: ·无向图的邻接矩阵对称,可压缩存储;有n个顶点的无 向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称;有n个顶点的有向图需存 储空间为n2 无向图中顶点V的度TDVi)是邻接矩阵A中第i行元素 之和 有向图中, 顶点Vi的出度是A中第i行元素之和 顶点Ⅴ的入度是A中第列元素之和 意·网络的邻接矩阵可定义为 4n=(0,若,y)成<y,y∈F 0,其它 计算机教研宦 第16页 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第16页 ▪ 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无 向图需存储空间为n(n+1)/2 ▪ 有向图邻接矩阵不一定对称；有n个顶点的有向图需存 储空间为n² ▪ 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素 之和 ▪ 有向图中， ▪ 顶点Vi的出度是A中第i行元素之和 ▪ 顶点Vi的入度是A中第i列元素之和 ▪ 网络的邻接矩阵可定义为 特点： = 0，其它 ,若(v , v )或 v , v E(G) [ , ] i j i j i j A i j
例 006 t150564 5∞50∞2 06 6 6 ② 例① 05703 8 50048 70021 04206 38160 my,(v,V)或 <V1,V;>∈(G) 0,其它 计算机教研宦 第17页 2021/2/19
Data Structure 数据结构—— 第7章图和广义表 胡建华 2021/2/19 计算机教研室 第17 页 例 1 4 5 2 3 7 5 31 8 6 4 2 = 0，其它 ,若(v , v )或 v , v E(G) [ , ] i j i j i j A i j 3 8 1 6 0 0 4 2 0 6 7 0 0 2 1 5 0 0 4 8 0 5 7 0 3 4 2 6 0 3 6 0 6 5 5 0 2 1 5 0 5 6 4 6 0 5 3 0 6 1 5 0 1 2 3 4 5 0 1 2 3 4 5 例 1 5 64 3 2 6 5 1 3 56 6 4 2 5
图的数组邻接矩阵存储表示 # define nfinity INt max∥最大值o e# define maXⅤ ERTEX NUM20∥最大顶点个数 a typedefenum DG, DN, AG, AN Graph Kind ∥有向图有向网无向图无向网} G typedef struct Arc Cell t Ⅴ RType adj;∥ RType是顶点关系类型。 ∥0对无权图,用1或0表示相邻否;对带权图,则为权值类型。 InfoType*info;∥该弧相关信息的指针 ArcCell, AdjMatrix MAX VERTEX NUMIIMAX VERTEX NUMB typedef struct VertexType vexs[MAX VERTEX NUMI;∥顶点向量 AdjMatrix arcs, ∥邻接矩阵 int vexnum, arcum;∥图的当前顶点数和弧(边)数 GraphKind kind;∥图的种类标志 3 MGraph 计算机教研宦 第18页 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第18页 图的数组(邻接矩阵)存储表示 #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, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧(边)数 GraphKind kind; // 图的种类标志 } MGraph;
@图的邻接表存储表示 邻接表是图的一种链式存储结构。 在邻接表中,对图中的每个顶点建立一个单链表,存储该顶点所有邻接点及 其关系信息。 每个单链表设一个头结点,称为顶点结点。单链表中的结点称为表结点,第 i个结点表示该顶点的第个邻接点。 对于具有n个顶点的图来说,其邻接表是由n个链表组成的。 每个链表的顶点结点包括两个域 Vertex域存放顶点的数据信息 例(ab FirstArc域指出依附于该顶点的第一条弧(或边)。 表结点由三个域组成,其中 adjvex域存放相邻接顶点的位置 info域存放相应的弧或边信息(包括权值),对于无带权图, GI 如果没有与边相关的其它信息,可省略此域 NextArc域指向下一个表结点。 顶点结点: Vertex FirstArc 表结点: Adjvex Info NextArc 计算机教研宦 第19页 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第19页 图的邻接表存储表示 ▪ 邻接表是图的一种链式存储结构。 ▪ 在邻接表中，对图中的每个顶点建立一个单链表，存储该顶点所有邻接点及 其关系信息。 ▪ 每个单链表设一个头结点，称为顶点结点。单链表中的结点称为表结点，第 i个结点表示该顶点的第i个邻接点。 ▪ 对于具有n个顶点的图来说，其邻接表是由n个链表组成的。 ▪ 每个链表的顶点结点包括两个域: Vertex域存放顶点的数据信息 FirstArc域指出依附于该顶点的第一条弧（或边）。 ▪ 表结点由三个域组成，其中 adjvex域存放相邻接顶点的位置 info域存放相应的弧或边信息（包括权值），对于无带权图， 如果没有与边相关的其它信息，可省略此域 NextArc域指向下一个表结点。 顶点结点： Vertex FirstArc 表结点： Adjvex Info NextArc 例 G1 b d a c
@°顶点结点和表结点的结构如下所示: 顶点结点: Vertex FirstArc 表结点: Adjvex Info NextArc vexdata firstarc adjvex next 例 234 abcd 4 GI vexdata firstarc adjvex next 例(a(b 4 abcde 5 2345 2 4 5 G2 2 算机教研室 第20页 2021/2/19
Data Structure 数 据 结 构—— 第 7 章 图 和 广 义 表 胡建华 2021/2/19 计算机教研室 第20页 • 顶点结点和表结点的结构如下所示: 顶点结点： Vertex FirstArc 表结点： Adjvex Info NextArc 例 G1 b d a c 例 a e c b d G2 1 2 3 4 a c d b vexdata firstarc 3 2 4 1 ^ ^ ^ ^ adjvex next 1 2 3 4 a c d b vexdata firstarc 4 2 1 2 ^ ^ ^ adjvex next 5 e 4 1 3 5 ^ 5 3 2 3 ^