图的存储结构

图的存储结构第1页，课件共25页，创作于2023年2月一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示7.2图的存储结构第2页，课件共25页，创作于2023年2月￡7.2图的存储结构￡7.2.1数组表示法（邻接矩阵）

（1）定义数组表示法：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。（2）C语言描述

#define INFINITY INT_MAX //最大值∞

#define MAX_VERTEX_NUM 20 //最大顶点个数

typedefenum{DG,DN,UDG,UDN}GraphKind; //{有向图，有向网，无向图，无向网} typedefstructArcCell{ VRType adj; //VRType是顶点关系类型。对无权图，用1 //或0表示相邻否；对带权图，则为权值类型。

InfoType *info; //该弧相关信息的指针

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct{ VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

AdjMatrix arcs; //邻接矩阵

int vexnum,arcnum; //图的当前顶点数和弧数

GraphKind kind; //图的种类标志

}MGraph;第3页，课件共25页，创作于2023年2月Aij={0(i,j)VR1(i,j)VRBACDFE定义:矩阵的元素为第4页，课件共25页，创作于2023年2月有向图的邻接矩阵为非对称矩阵ABECD第5页，课件共25页，创作于2023年2月在有向图中,统计第i行1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。在无向图中,统计第i

行(列)1的个数可得顶点i

的度。第6页，课件共25页，创作于2023年2月（3）邻接矩阵中顶点度的求法对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和，即：

对于有向图，顶点vi的出度OD(vi)为第i行的元素之和，顶点vi的入度ID(vi)为第j列的元素之和。（4）网的邻接矩阵网的邻接矩阵可定义为：

wi,j

若<vi,vj>或(vi,vj)∈VRA[i][j]=

∞

反之例如，下图列出了一个有向网和它的邻接矩阵。

(b)邻接矩阵(a)网N45387

9

1655

V1V2

V6V3V5V4第7页，课件共25页，创作于2023年2月（5）图的构造算法7.1如下：

StatusCreateGraph(MGraph&G){ //采用数组（邻接矩阵）表示法，构造图G。

scanf(&G.kind); switch(G.kind){ caseDG: returnCreateDG; //构造有向图G caseDN: returnCreateDN; //构造有向网G caseUDG: returnCreateUDG; //构造无向图G caseUDG: returnCreateUDG; //构造无向网G default: returnERROR; }}//CreateGraph算法7.1是在邻接矩阵存储结构MGraph上对图的构造操作的实现框架，它根据图G的种类调用具体构造算法。第8页，课件共25页，创作于2023年2月

StatusCreateUDN(MGraph&G){ //采用数组（邻接矩阵）表示法，构造无向网G。

scanf(&G.vexnum,&G.arcnum,&IncInfo); //IncInfo为0则各弧不含其他信息

for(i=0;i<G.vexnum;++i) scanf(&G.vexs[i]); //构造顶点向量

for(i=0;i<G.vexnum;++i) //初始化邻接矩阵

for(j=0;j<G.vexnum;++j) G.arcs[i][j]={INFINITY,NULL}; //{adj,info} for(k=0;k<G.arcnum;++k){ //构造邻接矩阵

scanf(&v1,&v2,&w); //输入一条边依附的顶点及权值

i=LocateVex(G,v1); //确定v1和v2在G中位置

j=LocateVex(G,v2); G.arcs[i][j].adj=w; //弧<v1,v2>的权值

if(IncInfo) Input(*G.arcs[i][j].info); //若弧含有相关信息，则输入

G.arcs[j][i]=G.arcs[i][j]; //置<v1,v2>的对称弧<v2,v1> }//for returnOK;}//CreateUDN算法7.2如下：算法7.2构造一个具有n个顶点和e条边的无向网G。其时间复杂度为O(n2+e*n)，其中对邻接矩阵G.arcs的初始化耗费了O(n2)的时间。第9页，课件共25页，创作于2023年2月7.2.2邻接表表示法(AdjacencyList)

用邻接矩阵存储弧或边的信息，比较浪费空间，如果我们只存储图中已有的弧或边的信息，就可以节省空间。而图中所有顶点都是依附于某两个顶点的，因此如果对图中的所有顶点都建立一个单链表来存储所有依附于该顶点的弧或边，就可以把图中所有已有的弧或边的信息保存下来。而对于图中所有顶点还是使用一个一维数组来存放。这种存储方法就是邻接表表示法。在邻接表表示法中，对于顶点单元i，需要存放的内容有顶点信息以及指向依附于该顶点的第一条弧或边的指针，用这个指针来指向依附于顶点i的所有的弧或边组成的单链表。对于弧单元，需要存放该弧指向的顶点的位置（也就是该弧依附的另一个顶点的位置）和指向依附于该弧的弧尾顶点的下一条弧的指针。对于弧和顶点分别可以用如下的结构实现：第10页，课件共25页，创作于2023年2月￡7.2.2邻接表（1）定义

邻接表（AdjacencyList）：是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。逆邻接表：即对每个顶点vi建立一个链接以vi为头的弧的表。在逆邻接表中可以方便的确定顶点的入度或以顶点vi为头的弧。（2）结点结构头结点datafirstarc表结点adjvexnextarcinfo表结点由3个域组成：

adjvex：邻接点域，指示与顶点vi邻接的点在图中的位置。

nextarc：链域，指示下一条边或弧的结点。

info：数据域，存储和边或弧相关的信息，如权值等。头结点由2个域组成：

data：数据域，存储顶点vi的名或其他有关信息。

firstarc：链域，指向链表中第一个结点。表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的链表。第11页，课件共25页，创作于2023年2月

#define MAX_VERTEX_NUM 20 typedefstructArcNode{ int adjvex; //该弧所指向的顶点的位置

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

InfoType *info; //该弧相关信息的指针

}ArcNode; typedefstructVNode{ VertexType data; //顶点信息

structArcNode*firstarc; //指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct{ AdjList vertices; int vexnum,arcnum; //图的当前顶点数和弧数

kind kind; //图的种类标志

}ALGraph;

（3）C语言描述第12页，课件共25页，创作于2023年2月（4）图形表示(a)有向图和无向图G1G2G1V1V2V3V4G2V1V2V4V5V3

(b)G1的邻接表V1V2V3V401232 130V1V2V3V401232003(c)G1的逆邻接表第13页，课件共25页，创作于2023年2月

(d)G2的邻接表图7.6邻接表和逆邻接表

对于无向图，顶点vi的度恰为第i个链表中的结点数。 对于有向图，顶点vi的出度OD(vi)为第i个链表中的结点个数；求顶点vi的入度ID(vi)必须遍历整个邻接表，查找所有链表中其邻接点域的值为i的结点，它们的总和即为顶点vi的入度。（5）邻接表中顶点度的求法V1V2V3V40123V54312120424310第14页，课件共25页，创作于2023年2月DBACFE

A14

B045

C35

D25

E01

F123012345在无向图的邻接表中，顶点Vi的度恰为第i个链表中的结点数。第15页，课件共25页，创作于2023年2月有向图的邻接表142301201234

ABCDEABECF可见，在有向图的邻接表中不易找到指向该顶点的弧第16页，课件共25页，创作于2023年2月ABECD有向图的逆邻接表ABCDE30342001234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧第17页，课件共25页，创作于2023年2月￡7.2.3十字链表（有向图）（1）定义十字链表（OrthogonalList）：是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧头相同的弧在同以一链表上，弧尾相同的弧也在同一链表上（2）结点结构弧结点头结点（顶点结点）datafirstinfirstouttailvexheadvexhlinktlinkinfo弧结点由5个域组成：

tailvex：尾域，指示弧尾顶点在图中的位置。

headvex：头域，指示弧头顶点在图中的位置。

hlink：链域，指向弧头相同的下一条弧。

tlink：链域，指向弧尾相同的下一条弧。

info：数据域，指向该弧的相关信息。头结点由3个域组成：

data：数据域，存储和顶点相关的信息，如顶点名称等。

firstin：链域，指向以该顶点为弧头的第一个弧结点。

firstout：链域，指向以该顶点为弧尾的第一个弧结点。第18页，课件共25页，创作于2023年2月三、有向图的十字链表存储表示

ABCABC012∧02∧∧0121∧20∧∧从横向上看是邻接表，从纵向上看是逆邻接表。第19页，课件共25页，创作于2023年2月

#define MAX_VERTEX_NUM 20 typedefstructArcBox{ int tailvex,headvex; //该弧的尾和头顶点的位置

structArcBox*hlink,*tlink; //分别为弧头相同和弧尾相同的弧的链域

InfoType *info; //该弧相关信息的指针

}ArcBox; typedefstructVexNode{ VertexType data; ArcBox *firstin,*firstout; //分别指向该顶点第一条入弧和出弧

}VexNode; typedefstruct{ VexNode xlist[MAX_VERTEX_NUM]; //表头向量

int vexnum,arcnum; //有向图的当前顶点数和弧数

}OLGraph;

（3）C语言描述第20页，课件共25页，创作于2023年2月（4）图形表示图7.7 有向图的十字链表V1V2

(a)V3V4

V1(b)

01V2

1V3

2V4

3

02

20

30

23

31

32

0第21页，课件共25页，创作于2023年2月（5）图的构造

StatusCreateDG(OLGraph&G){ //采用十字链表存储表示，构造有向图G(G.kind=DG)。

scanf(&G.vexnum,&G.arcnum,&IncInfo); //IncInfo为0则各弧不含其他信息

for(i=0;i<G.vexnum;++i){ //构造表头向量

scanf(&G.xlist[i].data); //输入顶点值

G.xlist[i].firstin=NULL; //初始化指针

G.xlist[i].firstout=NULL; } for(k=0;k<G.arcnum;++k){ //输入各弧并构造十字链表

scanf(&v1,&v2); //输入一条弧的始点和终点

i=LocateVex(G,v1); //确定v1和v2在G中位置

j=LocateVex(G,v2); p=(ArcBox*)malloc(sizeof(ArcBox)); //假定有足够空间 *p={i,j,G.xlist[j].firstin,G.xlist[j].firstout,NULL}; //对弧结点赋值{tailvex,headvex,hlink,tlink,info} G.xlist[j].firstin=G.xlist[j].firstout=p; //完成在入弧和出弧链头的插入

if(IncInfo) Input(*p－>info); //若弧含有相关信息，则输入

}//for}//CreateDG算法7.3如下：第22页，课件共25页，创作于2023年2月￡7.2.4邻接多重表（无向图）（1）定义邻接多重表（AdjacencyMultilist）：是无向图的另一种链式存储结构。邻接多重表的结构和十字链表类似。在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附两个顶点，则每个边结点同时链接在两个链表中。（2）结点结构边结点markivexilinkjvexjlinkinfodatafirstedge顶点结点边结点由6个域组成：

mark：标志域，用以标记该条边是否被搜索过。

ivex和jvex：为该边依附的两个顶点在图中的位置。

ilink：链域，指向下一条依附于顶点ivex的边。

jlink：链域，指向下一条依附于顶点jvex的边。

info：数据域，指向和边相关的各种信息的指针域。在邻接多重表中,每一条边用一个结点表示,每一个顶点也用一个结点表示。顶点结点有2个域组成：

data：数据域，存储和该顶点相关的信息。

firstedge：链域，指示第一条