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

1、图的几种存储结构比较研究图的几种存储结构比较研究 班级：班级： 软件工程六班软件工程六班 姓名：姓名： 马马 盛盛 国国 学号：学号：140120010168图的几种主要存储结构图的几种主要存储结构 1.邻接矩阵2.邻接表 3.十字链表 4.邻接多重表 上图中：上图中：D(1)=2D(2)=3D(3)=2 D(4)=3D(5)=2njjiavDi1,)(njija1,njjia1,邻接矩阵表示法中图的类型定义：邻接矩阵表示法中图的类型定义：#define MAXSIZE 100 /*图的顶点个数图的顶点个数*/typedef struc int no; /顶点编号顶点编号 infotype i

2、nfo; /顶点其它信息顶点其它信息vertextype; / 顶点类型顶点类型typedef struct /图的定义图的定义 vertextype vexsMAXSIZE； /*顶点信息表顶点信息表*/ int edgesMAXSIZE MAXSIZE ;/ *邻接矩阵邻接矩阵*/ int n ； /*顶点数顶点数*/ int e ； /*边数边数*/ mgraph；注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数

3、Typedef enum DG, DN, AG,AN GraphKind; /有向有向/ /无向图，有向无向图，有向/ /无向网无向网Typedef struct ArcCell /弧（边）弧（边）结点的定义结点的定义 VRType adj; /顶点间关系，无权图取顶点间关系，无权图取1 1或或0 0；有权图取权值类型；有权图取权值类型 InfoType *info; /该弧相关信息的指针该弧相关信息的指针ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;Typedef struct /图的定义图的定义VertexType vexs MAX_V

4、ERTEX_NUM ; /顶点表，用一维向量即可顶点表，用一维向量即可AdjMatrix arcs; /邻接矩阵邻接矩阵Int Vernum, arcnum; /顶点总数，弧（边）总数顶点总数，弧（边）总数GraphKind kind; /图的种类标志图的种类标志Mgraph; 图的邻接矩阵存储表示（参见教材P161）对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n=O(n2 2) )Status CreateUDN(Mgraph &G) /无向网的构造，用邻接矩阵表示无向网的构造，用邻接矩阵表示scanf(&G.vexnum, &G.arcnum

5、, &IncInfo); /输入总顶点数，总弧数和信息输入总顶点数，总弧数和信息for(i=0;iG.vexnum,;+i) scanf(&G.vexsi );/);/输入顶点值，存入一维向量中输入顶点值，存入一维向量中for(i=0; iG.vexnum; +i) /对邻接矩阵对邻接矩阵n n* *n n个单元初始化，个单元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL; for(k=0;kG.arcnum;+k) /给邻接矩阵有关单元赋初值给邻接矩阵有关单元赋初值( (循环次数弧数循环次数弧数

6、 scanf(&v1, &v2, &w); /输入弧的两顶点以及对应权值输入弧的两顶点以及对应权值 i=LocateVex(G,v1); j=LocateVex(G,v2); /找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n(n次次? ? G.arcsij.adj=w; /输入对应权值输入对应权值 If(IncInfo) Input(*G.); /如果弧有信息则填入如果弧有信息则填入 G.arcsij = G.arcs j i； /无向网是对称矩阵无向网是对称矩阵 return OK; / / CreateUDN 例：用邻接矩阵生成无向网的算

7、法对于对于n个顶点个顶点e条弧的网，条弧的网，建网时间效率建网时间效率 = O(n2+n+e*n)表结点表结点表头结点表头结点假设数组下标自假设数组下标自1开始开始2 13 V1V2V32 1 2 G123123adjvexinfonextareadjvex：顶点号：顶点号info：边上所带的权：边上所带的权nextare：指针：指针图的邻接表存储表示#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef struct ArcNode int adjvex; /该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode *nextarc

8、s; /指向下一条弧的指针指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针该弧相关信息的指针 ArcNode；Typedef struct VNode /顶点结构顶点结构 VertexType data; /顶点信息顶点信息 ArcNode * firstarc; /指向依附该顶点的第一条弧的指针指向依附该顶点的第一条弧的指针VNode, AdjList MAX_VERTEX_NUM ; Typedef struct /图结构图结构 AdjList vertics ; /应包含邻接表应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数应包含顶点总

9、数和弧总数 int kind; /还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph; /图结构图结构空间效率为空间效率为O(n+2e)或或O(n+e)时间效率为时间效率为O(n+e) 它是它是有向图有向图的另一种链式结构。的另一种链式结构。 思路：思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1 1、每条弧对应一个结点、每条弧对应一个结点( (称为称为弧结点弧结点，设设5 5个域）个域）2 2、每个顶点也对应一个结点（称为、每个顶点也对应一个结点（称为顶点结点顶点结点，设设3 3个域）个域）tailvexheadvexH

10、linktlinkinfo顶点结点顶点结点弧结点弧结点三、十字链表tailvex: 弧尾顶点位置 headvex: 弧头顶点位置hlink: 弧头相同的下一弧位置tlink: 弧尾相同的下一弧位置info: 弧信息 n个顶点个顶点用顺序存储结构用顺序存储结构 data : 存储顶点信息。存储顶点信息。Firstin : 以顶点为弧头的第一条弧结点。Firstout: 以顶点为弧尾的第一条弧结点。dataFirstinFirstout适用于有向图适用于有向图#define MAX_VERTEX_NUM 20Typedef struct ArcBox /弧结点结构弧结点结构 int tailvex

11、 , headvex ; struct ArcBox * hlink , *tlink; InfoType *info; ArcBox；Typedef struct VexNode /顶点结构顶点结构 VertexType data; ArcBox * firstin,*firstout;VexNode; Typedef struct VexNode xlist MAX_VERTEX_NUM ; /表头向量表头向量 int vexnum, arcnum;OLGraph; /图结构图结构十字链表存储结构描述：0v11v22v33v4v1v2v3v40 1022 023例：画出有向图的十字链表。十

12、字链表优点：十字链表优点：容易操作，如求顶点的入度、出度等。容易操作，如求顶点的入度、出度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。303132数组下标不数组下标不属结点分量属结点分量这是这是无向图无向图的另一种存储结构，当对边操作时，无向图应采用的另一种存储结构，当对边操作时，无向图应采用此种结构存储。此种结构存储。 1 1、每条边只对应一个结点（称为、每条边只对应一个结点（称为边结点边结点），设立），设立6 6个域个域；2 2、每个顶点也对应一个结点（、每个顶点也对应一个结点（顶点结点顶点结点），设立），设立2 2个域；

13、个域；markivexilinkjvexjlinkinfo边结点边结点四、邻接多重表mark：标志域，如处理过或搜索过。：标志域，如处理过或搜索过。ivex，jvex : 顶点域，边依附的两个顶点位置顶点域，边依附的两个顶点位置 ilink: 指向下一条依附顶点指向下一条依附顶点 i 的边结点位置。的边结点位置。Jlink: 指向下一条依附顶点指向下一条依附顶点 j 的边结点位置。的边结点位置。info: 边信息，如权值等。边信息，如权值等。n个顶点个顶点用顺序存储结构用顺序存储结构 data : 存储顶点信息。存储顶点信息。Firstedge : 依附顶点的第一依附顶点的第一条边结点。条边结点。dataFirstedge顶点结点顶点结点适用于无向图适用于无向图0v11v22v33v44v501031214232434v1v2v3v5v4v4例：画出无向图的邻接多重表邻接多重表优点：邻接多重表优点：容易操作，如求顶点的度等。容易操作，如求顶点的度等。 空间复杂度与邻接表相同；空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。建立的时间复杂度与邻接表相同。数组下标不数组下标不属结点分量