数据结构39-图的存储结构.pptVIP

数 据 结 构第三十九课 图的存储结构 第三十一课 图的存储结构 本课主题： 图的存储结构 教学目的： 掌握图的二种存储表示方法 教学重点： 图的数组表示及邻接表表示法 教学难点： 邻接表表示法 授课内容： 一、数组表示法 1﹑邻接矩阵的定义有n个顶点的图G=(V,{VR})的邻接矩阵为n阶方阵，其定义为： 2﹑无向图邻接矩阵的性质 无向图的邻接矩阵是对称矩阵； 顶点vi的度是邻接矩阵中第i行（或第i列）的元素(1)之和。 3﹑有向图邻接矩阵的性质 有向图的邻接矩阵不一定是对称矩阵； 顶点vi的出度是邻接矩阵中第i行元素之和，入度是邻接矩阵中第i列的元素之和 4﹑网的邻接矩阵 将邻接矩阵中的0、1换成权值，就是网的邻接矩阵。 5﹑邻接矩阵的优缺点 优点: 容易实现图的前4个操作, 即判定顶点间有无边（弧），容易计算顶点的度（出度、入度）； 缺点: 所占空间只和顶点个数有关，和边数无关，在边数较少时，空间浪费较大。 6﹑图的抽象数据类型—数组（邻接矩阵）存储表示(1) #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]; 6﹑图的抽象数据类型—数组（邻接矩阵）存储表示(2) tpyedef struct{ VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph; 7﹑建立邻接矩阵的算法(1) #define MAX N /*定义最大顶点个数N为某一正整数 */ typedef struct { datatype vaxs[MAX+1]; /* 一维数组存放各顶点的值 */ int arcs[MAX+1][MAX+1]; /* 定义二维数组存放邻接矩阵 */ int vexnum,arcnum; /* 图中实际顶点数和边（弧）数 */ } mgraph; 7﹑建立邻接矩阵的算法(2) void creatgraph(g) mgraph g; { int i,j,k,vl,v2; int LocateVex( ); /* 具体内容见下面算法 */ scanf(%d,%d,g-vexnum,g-arcnum);/* 输入图g的顶点数和边数*/ for (i=1;i=g-vexnum;i++) scanf(“%d”,g-vexs[i]); /* 输入各顶点值，设为int型 */ 7﹑建立邻接矩阵的算法(3) for (i=1;i=g-vexnum;i++) for(j=l;j=g-vexnum;j++) g-arcs[i][j]=0; /*初始化邻接矩阵 */ for(k=l;k=g-arcnum;k++) { scanf(%d,%d,vl,v2); /* 依次输入每条边关联的两个顶点的值:若顶点值不是int型，*/ /* 则应设置成其他的格式字串 */ i=LocateVex(g,v1);j=LocateVex(g,v2); / *确定两个顶点在图中的位置序号分别为i,j */ if (i!=0 j!=0) /* 如果输入的顶点在图中，则对邻接矩阵中 */ { g-arcs[i][j]=l; /* 的相应位置及其对称位置的元素赋值为l*/ g-arcs[i][j]=1; } } 7﹑建立邻接矩阵的算法(4) int LocateVex(mgraph *g , int v) { int i; for (i=1;g-vexs[i]!=v i=g-vexnum; i++); /* 查顶点v的下标i */ if (ig-vexnum) return(0); else return(i); } 二、邻接表邻接矩阵在稀疏图时空间浪费较大，为了克服这一缺点, 2﹑邻接表是顶点的向量结构和边（弧）的单链表结构 每个顶点结点包括两个域，将n个顶点放在一个向量中（