图的几种存储结构比较分析

图的几种存储结构比较研究

班级：软件工程六班

姓名：马盛国

学号：140120010168图的几种主要存储结构

1.邻接矩阵2.邻接表3.十字链表4.邻接多重表

1.邻接矩阵

对于无向图，(vi,vj)和(vj,vi)表示同一条边，因此，在邻接矩阵中aij=aji。对有向图，弧<vi,vj>和<vj,vi>表示方向不同的两条弧，所以aij≠aji。

在图的顶点确定的情况下，其邻接矩阵表示是唯一的。邻接矩阵(AdjacencyMatrix)是表示图中顶点之间相邻关系的矩阵。设G＝(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵An×n：

无向图的邻接矩阵是以主对角线对称的，第i行(列)1的个数就是顶点vi

的度。即上图中：D(1)=2 D(2)=3 D(3)=2 D(4)=3 D(5)=2

有向图的邻接矩阵可能是不对称的。在有向图中：▲第i

行中1的个数就是顶点i

的出度。▲第j列中1的个数就是顶点j

的入度。▲有向图中各顶点的入度之和等于出度之和。ID(vi)=

OD(vi)=

上图中：D(1)=OD(1)+ID(1)=3D(2)=OD(2)+ID(2)=3 D(3)=OD(3)+ID(3)=3D(4)=OD(4)+ID(4)=3 ■带权值的邻接矩阵总结：（1）因为不考虑顶点到自身的边或弧，所以邻接矩阵的对角线必为0；（2）无向图的邻接矩阵为对称矩阵，所以可用特殊矩阵压缩方式存储；（3）无向图的顶点的度为邻接矩阵中该顶点对应的行(列)中非零元个数；（5）有向图的邻接矩阵不一定为对称矩阵;（6）有向图中顶点的入度为该顶点对应列中非零元的个数，出度为该顶点对应行中为非零元的个数。邻接矩阵表示法中图的类型定义：#defineMAXSIZE100/*图的顶点个数*/typedefstruc{intno;//顶点编号

infotypeinfo;//顶点其它信息}vertextype;//顶点类型typedefstruct//图的定义{vertextypevexs[MAXSIZE]；/*顶点信息表*/intedges[MAXSIZE][MAXSIZE];/*邻接矩阵*/intn；/*顶点数*/inte；/*边数*/}mgraph；21435无向图t->n=5t->e=6mgraph*t;BADCE有向图mgraph*t;t->n=5t->e=6注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假设的最大顶点数Typedefenum{DG,DN,AG,AN}GraphKind;

//有向/无向图，有向/无向网Typedefstruct

ArcCell{//弧（边）结点的定义

VRTypeadj;//顶点间关系，无权图取1或0；有权图取权值类型

InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可AdjMatrixarcs;//邻接矩阵IntVernum,arcnum;//顶点总数，弧（边）总数GraphKindkind;//图的种类标志}Mgraph;

图的邻接矩阵存储表示（参见教材P161）对于n个顶点的图或网，空间效率=O(n2)StatusCreateUDN(Mgraph&G){//无向网的构造，用邻接矩阵表示scanf(&G.vexnum,&G.arcnum,&IncInfo);//输入总顶点数，总弧数和信息for(i=0;i<G.vexnum,;++i)scanf(&G.vexs[i]);//输入顶点值，存入一维向量中for(i=0;i<G.vexnum;++i)//对邻接矩阵n*n个单元初始化，adj=∞,info=NULLfor(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){

//给邻接矩阵有关单元赋初值(循环次数＝弧数

scanf(&v1,&v2,&w);

//输入弧的两顶点以及对应权值

i=LocateVex(G,v1);j=LocateVex(G,v2);

//找到两顶点在矩阵中的位置(n次?

G.arcs[i][j].adj=w;

//输入对应权值

If(IncInfo)Input(*G.arcs[i][j].info);

//如果弧有信息则填入

G.arcs[i][j]=G.arcs[j][i]；

//无向网是对称矩阵

}returnOK;}//CreateUDN

例：用邻接矩阵生成无向网的算法对于n个顶点e条弧的网，建网时间效率=O(n2+n+e*n)7.2.2邻接表

邻接表是图的一种链式存储结构。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。

因此邻接表是由单链表的表头形成的顶点表和单链表其余结点形成的边表两部分组成。图的邻接表表表示不唯一。

图的链式存储结构特征：（1）为每个顶点建立一个单链表；（2）第i个单链表中包含顶点Vi的所有邻接顶点。

无向图的邻接表(不带权)表结点表头结点datafirstareadjvexnextare

每个链表的前边附设一个表头结点。把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点。假设数组下标自1开始1234

有向图的邻接表和逆邻接表2^13^V1V2V3^2^1^2^V1V2V3G邻接表逆邻接表v1v2v3123123在有向图的邻接表中，第i

个边链表链接的边都是顶点i

发出的边。也叫做出边表。在有向图的逆邻接表中，第i

个边链表链接的边都是进入顶点i

的边。也叫做入边表。邻接表的类型定义说明：在邻接表的边链表中，各个表结点的链入顺序任意，视表结点输入次序而定(不唯一)。设图中有

n

个顶点，e

条边，则用邻接表表示无向图时，需要

n个表头结点，2e个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个表头结点，e个表结点。带权图的边表结点中还应保存该边上的权值

info。网络(带权图)的邻接表边表结点adjvexinfonextareadjvex：顶点号info：边上所带的权nextare：指针图的邻接表存储表示#defineMAX_VERTEX_NUM20//假设的最大顶点数TypedefstructArcNode{

intadjvex;//该弧所指向的顶点位置

structArcNode*nextarcs;//指向下一条弧的指针

InfoArc*info;//该弧相关信息的指针}ArcNode；TypedefstructVNode{

//顶点结构

VertexTypedata;//顶点信息

ArcNode*firstarc;//指向依附该顶点的第一条弧的指针}VNode,AdjList[MAX_VERTEX_NUM];

Typedefstruct{//图结构

AdjListvertics;//应包含邻接表

intvexnum,arcnum;//应包含顶点总数和弧总数

intkind;//还应说明图的种类（用标志）}ALGraph;

//图结构空间效率为O(n+2e)或O(n+e)时间效率为O(n+e)

它是有向图的另一种链式结构。

思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、每条弧对应一个结点(称为弧结点，设5个域）2、每个顶点也对应一个结点（称为顶点结点，设3个域）tailvexheadvexHlinktlinkinfo顶点结点弧结点三、十字链表tailvex:

弧尾顶点位置headvex:

弧头顶点位置hlink:

弧头相同的下一弧位置tlink:

弧尾相同的下一弧位置info:

弧信息n个顶点—用顺序存储结构data:存储顶点信息。Firstin:

以顶点为弧头的第一条弧结点。Firstout:

以顶点为弧尾的第一条弧结点。dataFirstinFirstout——适用于有向图#defineMAX_VERTEX_NUM20TypedefstructArcBox{//弧结点结构

inttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;}ArcBox；TypedefstructVexNode{//顶点结构

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;Typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//表头向量

intvexnum,arcnum;}OLGraph;//图结构十字链表存储结构描述：0v11v22v33v4v1v2v3v4010^2202^^3例：画出有向图的十字链表。十字链表优点：容易操作，如求顶点的入度、出度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。3^03^^13^^2^数组下标不属结点分量这是无向图的另一种存储结构，当对边操作时，无向图应采用此种结构存储。

1、每条边只对应一个结点（称为边结点），设立6个域；2、每个顶点也对应一个结点（顶点结点），设立2个域；markivexilinkjvexjlinkinfo边结点四、邻接多重表