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

数据结构

第三十九课图的存储结构第三十一课图的存储结构本课主题：图的存储结构教学目的：掌握图的二种存储表示方法教学重点：图的数组表示及邻接表表示法教学难点：邻接表表示法授课内容：一、数组表示法用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。1﹑邻接矩阵的定义

有n个顶点的图G=(V,{VR})的邻接矩阵为n阶方阵，其定义为：2﹑无向图邻接矩阵的性质无向图的邻接矩阵是对称矩阵；顶点vi的度是邻接矩阵中第i行（或第i列）的元素(1)之和。3﹑有向图邻接矩阵的性质有向图的邻接矩阵不一定是对称矩阵；顶点vi的出度是邻接矩阵中第i行元素之和，入度是邻接矩阵中第i列的元素之和4﹑网的邻接矩阵将邻接矩阵中的0、1换成权值，就是网的邻接矩阵。5﹑邻接矩阵的优缺点优点:容易实现图的前4个操作,即判定顶点间有无边（弧），容易计算顶点的度（出度、入度）；缺点:所占空间只和顶点个数有关，和边数无关，在边数较少时，空间浪费较大。6﹑图的抽象数据类型—数组（邻接矩阵）存储表示(1)#defineINFINITYINT_MAX//最大值无穷大#defineMAX_VERTEX_NUM20//最大顶点个数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];//顶点向量AdjMatrixarcs;//邻接矩阵int

vexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;6﹑图的抽象数据类型—数组（邻接矩阵）存储表示(2)7﹑建立邻接矩阵的算法(1)#defineMAXN/*定义最大顶点个数N为某一正整数*/typedef

struct{datatypevaxs[MAX+1];/*一维数组存放各顶点的值*/

intarcs[MAX+1][MAX+1];/*定义二维数组存放邻接矩阵*/

int

vexnum,arcnum;/*图中实际顶点数和边（弧）数*/}mgraph;7﹑建立邻接矩阵的算法(2)voidcreatgraph(g)mgraphg;{inti,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,intv){inti;for(i=1;g->vexs[i]!=v&&i<=g->vexnum;i++);/*查顶点v的下标i*/if(i>g->vexnum)return(0);elsereturn(i);}二、邻接表

邻接矩阵在稀疏图时空间浪费较大，为了克服这一缺点,可采用邻接表表示法。1﹑邻接表的结点结构（1）顶点结点结构（2）边（弧）结点结构其中，vexdata是顶点数据，firstarc是指向该顶点第一个邻接点的指针，adjvex是邻接点在向量中的下标，info是邻接点的信息，next是指向下一邻接点的指针。2﹑邻接表是顶点的向量结构和边（弧）的单链表结构每个顶点结点包括两个域，将n个顶点放在一个向量中（称为顺序存储的结点表）；一个顶点的所有邻接点链接成单链表，该顶点在向量中有一个指针域指向其第一个邻接点。3﹑邻接表的优缺点容易实现图的前4个操作；空间较省；无向图容易求各顶点的度；边表中结点个数是边的两倍；有向图容易求顶点的出度；若求顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）4﹑建立邻接表的算法(1)#defineMAXn/*定义最大顶点个数n为某一正整数*/typedef

struct

EdgeNode{int

adjnum;/*邻接点域，存储位置序号，为int型*/

DataTypeinfo;

struct

EdgeNode*nextarc;/*链域，指向下一条边(弧)的指针*/}EdgeNode;typedef

struct

VNode/*头结点的类型Vnode*/{DataType

vexdata;/*头结点的数据域*/struct

EdgeNode*link;/*头结点的指针域*/}VNode;4﹑建立邻接表的算法(2)typedef

VNode

AdGraph[MAX+l];/*定义图的类型AdGraph，为一个一维数组*/voidcreatgraph(g)AdGraphg;{int

i,n,e,*p=g,v1,v2;/*假设顶点数据为int型*/scanf("%d,%d",&n,&e);/*输入图g的顶点数n和边数e*/for(i=1;i<=n;i++){scanf(“%d”,p[i].vexdata);/*输入各顶点值，设为int型*/

p[i].link=null;}4﹑建立邻接表的算法(3)for(i=1;i<=e;i++)/*输入e条边*/{scanf("%d,%d",&v1,&v2);/*输入图g的顶点v1和v2*/i=LocateVex(g,v1);j=LocateVex(g,v2);/*确定两个顶点在图中的位置序号分别为i,j*/if(i!=0&&j!=0)/*如果输入的顶点在图中*/{r=(Vnode*)malloc(sizeof(Vnode))r->adjnum=j;r->nextarc=p[i]->link;/*链入i链表中*/

p[i]->link=r;r=(Vnode*)malloc(sizeof(Vnode))r->adjnum=i;r->nextarc=p[j]->link;/*链入j链表中*/

p[j]->link=r;}}5﹑图的十字链表表示法在有向图的邻接表表示法中，查每个顶点的出度非常容易，但查顶点的入度就要遍历整个邻接表。解决的办法是建立逆邻接表，但这成了两个表，也不方便。本节介绍有向图的另一种表示方法