7.2图的存储表示 一、图的数组（邻接矩阵）存储表示 二、 图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示
7.2 图的存储表示 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示
图的数组（邻接矩阵）存储表示 0,(VV)☐VR 定义：nxn矩阵的元素为A={1,仪，口VR 无向图 1 2 V3 2 3 V1 4 V4 5 V6 5 无向图的邻接矩阵是对称矩阵
A[i][j]={ 0 , (vi ,vj ) VR 1 , (vi ,vj ) VR 一、图的数组(邻接矩阵)存储表示 定义: n×n矩阵的元素为 1 2 3 4 5 6 1 2 3 4 5 6 V1 V2 V3 V4 V6 V5 无向图 无向图的邻接矩阵是对称矩阵
网的予接矩阵存储表示 定义：xn矩阵的元素为A{ Wii,(V,Y)▣VR ,(ViV)VR 无向网 2 3 4 5 6 V3 1 15 ∞ 11 15 25 2 15 ∞ ∞ ∞ 6 7 3 ∞ ∞ 25 ∞ 2 V4 4 25 ∞ ∞ 12 12 5 ∞ ∞ ∞ V5 6 12 ∞ 显然，无向网的邻接矩阵也是对称矩阵
网的邻接矩阵存储表示 定义: n×n矩阵的元素为 无向网 V1 V2 V3 V4 V6 V5 15 6 7 11 2 25 12 1 2 3 4 5 6 1 2 3 4 5 6 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 Aij= { wi,j ,(vi ,vj ) VR ,(vi ,vj 8 ) VR 显然，无向网的邻接矩阵也是对称矩阵。 8
有向图的邻接矩阵 为非对称矩阵 234 5 出度 5 出度？入度？ 食
有向图的邻接矩阵 为非对称矩阵 V1 V2 V4 V3 V5 出度？入度？ 出度 入 度 1 2 3 4 5 1 2 3 4 5
ypedef struct{∥图的定义 VertexType vexs[MAX VERTEX NUM]; ∥顶点向量，顶点信息 AdjMatrix arcs; ∥邻接矩阵，弧信息 int vexnum,arcnum; ∥顶点数，弧数 GraphKind kind; ∥图的种类标志 }MGraph; I∥DG,UDG,DN,UDN typedef struct ArcCell{∥弧的定义 VRType adj; I∥VRType,是顶点关系类型。 ∥对无权图，用1或0表示相邻否： ∥对带权图，则为权值类型。 InfoType *info; ∥该弧相关信息的指针 ArcCell,AdjMatrix[MAX VERTEX NUM] [MAX_VERTEX NUM]:I∥二维数组
typedef struct { // 图的定义 } MGraph; typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型。 // 对无权图，用1或0表示相邻否； // 对带权图，则为权值类型。 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM]; // 二维数组 VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量，顶点信息 AdjMatrix arcs; // 邻接矩阵 ，弧信息 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图的种类标志 // DG,UDG,DN,UDN