数据结构教程第二十八课图的存储结构

文章作者 100test 发表时间 2007:03:10 18:28:46
来源 100Test.Com百考试题网

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

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

教学难点： 邻接表表示法

授课内容：

一、数组表示法

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

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

#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.