第二十八课：图的存储结构

第二十八课

本课主题： 图的存储结构

教学目的： 掌握图的二种存储表示方法

教学重点： 图的数组表示及邻接表表示法

教学难点： 邻接表表示法

授课内容：

一、数组表示法

用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

// 图的数组（邻接矩阵）存储表示

#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];

tpyedef struct{

VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

AdjMatrix arcs; //邻接矩阵

int vexnum,arcnum; //图的当前顶点数和弧数

GraphKind kind; //图的种类标志

}MGraph;