数据结构第7章图.pptVIP

第七章图*017.1图的类型定义037.3图的遍历057.5有向无环图及其应用027.2图的存储结构047.4最小生成树067.6最短路径7.1图的类型定义*其中：V={ei|ei∈ElemSet,i=1,2,…,n}R={VR}VR={v,w|v,w∈V且P(v,w)}谓词P(v,w)定义了v,w之间关系的意义或信息。图是由一个顶点集V和一个关系集R构成的数据结构。Graph=(V,R)7.2图的存储表示*图的数组(邻接矩阵)存储表示有向图的十字链表存储表示图的邻接表存储表示无向图的邻接多重表存储表示一、邻接矩阵*在存储图的结构时，至少要保存两类信息：顶点的数据顶点之间的关系数组表示法：使用两个数组，其中一个用来存储顶点的数据，另一个用来存储顶点之间的关系(弧)，表示弧的矩阵被称为邻接矩阵（二维数组）。具有n个顶点的图G的邻接矩阵是具有如下性质的n阶矩阵：A[i][j]=1Vi邻接Vj（0≤i，j≤n-1）0Vi与Vj不邻接V1V2V3V4V1V5V4V2V301010010101011010001100无向图G2的邻接矩阵有向图G1的邻接矩阵011000000001000v1v2v3v4v1v2v3v4无向图邻接矩阵表示法特点：*无向图邻接矩阵是对称矩阵，同一条边表示了两次,无向图的总边数为非0元素个数的一半；顶点v的度:等于二维数组对应行（或列）中1的个数；判断两顶点v、u是否为邻接点:只需判断二维数组对应分量是否为1；顶点不变，在图中增加、删除边:只需对二维数组对应分量赋值1或清0；设图的顶点数为n,存储图用一维数组,数组元素有m（m=n)个,则G占用存储空间：m+n2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；无向图的邻接矩阵为对称矩阵。**有向图邻接矩阵表示法特点：有向图邻接矩阵不一定是对称矩阵；有向图的弧数是矩阵中1的个数。顶点v的出度：等于二维数组对应行中1的个数；顶点v的入度：等于二维数组对应列中1的个数；有向图的总弧数为非0元素个数。网的邻接矩阵:132458462∞5465∞∞84∞∞2682∞A=A[i][j]=wijVi邻接Vj,权值是Wij（0≤i，j≤n-1）∞Vi与Vj不邻接*图的数组存储表示#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,AG,AN}GraphKind;//{有向图,有向网,无向图,无向网}typedefstructArcCell{//存储弧/边的信息，即邻接矩阵VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];图的数组存储表示typedefstruct{//存储数据元素信息VertexTypevexs[MAX_VERTEX_NUM];//存储数据元素信息，即顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧(边)数GraphKindkind;//图的种类标志}MGraph;01邻接矩阵的数据类型定义02#defineMaxV100//定义最大顶点数03typedefstruct{ 04intvexes[MaxV];//顶点表05intedges[MaxV][MaxV];//邻接矩阵06intn,e;//顶点数n和边数e07}MGraph;二、邻接表*邻接表