最新图的存储结构精品课件.ppt

《最新图的存储结构精品课件.ppt》由会员分享，可在线阅读，更多相关《最新图的存储结构精品课件.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的存储结构图的存储结构一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示7.2 图的存储结构图的存储结构 Status CreateUDN (MGraph &G) /采用数组（邻接矩阵）表示法，构造无向网采用数组（邻接矩阵）表示法，构造无向网G。scanf (&G.vexnum, &G.arcnum, &IncInfo);/IncInfo为为0则各弧不含其他信息则各弧不含其他信息for (i = 0; i G.vexnum; + + i)scanf (&G.vexsi);/构造顶点向量构造顶点向量for (i = 0; i

2、G.vexnum; + + i)/初始化邻接矩阵初始化邻接矩阵for (j = 0; j G.vexnum; + + j)G.arcsij = INFINITY, NULL;/adj, infofor (k = 0; k G.arcnum; + + k) /构造邻接矩阵构造邻接矩阵scanf (&v1, &v2, &w);/输入一条边依附的顶点及权值输入一条边依附的顶点及权值i = LocateVex (G, v1);/确定确定v1和和v2在在G中位置中位置j = LocateVex (G, v2);G.arcsij.adj = w;/弧弧的权值的权值if (IncInfo)Input (*G

3、.arcsij.info);/若弧含有相关信息，则输入若弧含有相关信息，则输入G.arcsji = G.arcsij;/置置的对称弧的对称弧 / forreturn OK; / CreateUDN算法算法7.2如下：如下：算法算法7.2构造一个具有构造一个具有n个顶点和个顶点和e条边的无向网条边的无向网G。其时间复杂度为。其时间复杂度为O(n2+e*n)，其中对邻接矩，其中对邻接矩阵阵G.arcs的初始化耗费了的初始化耗费了O(n2)的时间。的时间。7.2.2邻接表表示法邻接表表示法(Adjacency List) 用邻接矩阵存储弧或边的信息，比较浪费空间，如果我们只存储图中已有的弧或边的信息

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

5、定义 邻接表（邻接表（Adjacency List）：是图的一种链式存储结构。在：是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的个单链表中的结点表示依附于顶点结点表示依附于顶点vi的边（对有向图是以顶点的边（对有向图是以顶点vi为尾的弧）。为尾的弧）。 逆邻接表：即对每个顶点逆邻接表：即对每个顶点vi建立一个链接以建立一个链接以vi为头的弧的表。为头的弧的表。在逆邻接表中可以方便的确定顶点的入度或以顶点在逆邻接表中可以方便的确定顶点的入度或以顶点vi为头的弧。为头的弧。 （2）结点结构）结点结构头结点头结点 data

6、 firstarc表结点表结点 adjvex nextarc info表结点由表结点由3个域组成：个域组成： adjvex：邻接点域，指示与顶点：邻接点域，指示与顶点vi邻接的点在图中的位置。邻接的点在图中的位置。 nextarc：链域，指示下一条边或弧的结点。：链域，指示下一条边或弧的结点。 info：数据域，存储和边或弧相关的信息，如权值等。：数据域，存储和边或弧相关的信息，如权值等。头结点由头结点由2个域组成：个域组成： data：数据域，存储顶点：数据域，存储顶点vi的名或其他有关信息。的名或其他有关信息。 firstarc：链域，指向链表中第一个结点。：链域，指向链表中第一个结点。表

7、头结点通常以表头结点通常以顺序结构的形式顺序结构的形式存储，以便随机存储，以便随机访问任一顶点的访问任一顶点的链表。链表。#defineMAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息顶点信息 struct ArcNode * firsta

8、rc;/指向第一条依附该顶点的弧的指针指向第一条依附该顶点的弧的指针 VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 kind kind;/图的种类标志图的种类标志 ALGraph; （3）C语言描述语言描述（4）图形表示）图形表示(a) 有向图有向图 和无向图和无向图 G1G2G1V1 V2V3 V4G2V1 V2V4 V5V3 (b) G1的邻接表的邻接表V1V2V3V40 1 2 3 2 1 30V1V2V3V40 1 2 3 20

9、03(c) G1的逆邻接表的逆邻接表 (d) G2的邻接表的邻接表图图7.6 邻接表和逆邻接表邻接表和逆邻接表对于无向图，顶点对于无向图，顶点vi的度恰为第的度恰为第i个链表中的结点数。个链表中的结点数。对于有向图，顶点对于有向图，顶点vi的出度的出度OD(vi)为第为第i个链表中的结点个数；求顶点个链表中的结点个数；求顶点vi的的 入度入度ID(vi)必须遍历整个邻接表，查找所有链表中其邻接点域的值为必须遍历整个邻接表，查找所有链表中其邻接点域的值为i的结点，的结点， 它们的总和即为顶点它们的总和即为顶点vi的入度。的入度。（5）邻接表中顶点度的求法）邻接表中顶点度的求法V1V2V3V40

10、1 2 3 V54 3 1 2 1 2 0 4 2 4 3 1 0 DBACFE A 1 4 B 0 4 5 C 3 5 D 2 5 E 0 1 F 1 2 30 1 2 3 4 5在无向图的邻接表中，在无向图的邻接表中，顶点顶点Vi的度恰为第的度恰为第i个个链表中的结点数。链表中的结点数。有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C D EABECF可见，在有向图的邻接表中不易找到指向该顶点的弧ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧7.2.3 十字链表（有向图

11、）十字链表（有向图）（1）定义）定义 十字链表（十字链表（Orthogonal List）：是有向图的另一种链式存储结构。可）：是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧头相同的弧在同以一链表上，弧尾相同的弧也在同一链表上头相同的弧在同以一链表上，弧尾相同的弧也在同一链表上 （2）结点结构）结点结构弧结点弧结点头结点（顶点结点）头结点（顶点结点）data firstin firstouttailvex headvex hlink tlink info 弧结点由弧结点由5个域组成

12、：个域组成：tailvex：尾域，指示弧尾顶点在图中的位置。：尾域，指示弧尾顶点在图中的位置。headvex：头域，指示弧头顶点在图中的位置。：头域，指示弧头顶点在图中的位置。hlink：链域，指向弧头相同的下一条弧。：链域，指向弧头相同的下一条弧。tlink：链域，指向弧尾相同的下一条弧。：链域，指向弧尾相同的下一条弧。info：数据域，指向该弧的相关信息。：数据域，指向该弧的相关信息。 头结点由头结点由3个域组成：个域组成：data：数据域，存储和顶点相关的信息，如顶点名称等。：数据域，存储和顶点相关的信息，如顶点名称等。firstin：链域，指向以该顶点为弧头的第一个弧结点。：链域，指向

13、以该顶点为弧头的第一个弧结点。firstout：链域，指向以该顶点为弧尾的第一个弧结点。：链域，指向以该顶点为弧尾的第一个弧结点。三、有向图的十字链表存储表示三、有向图的十字链表存储表示 ABCABC0 1 20 2 0 12 1 2 0 从横向上看是邻接表，从纵从横向上看是邻接表，从纵向上看是逆邻接表。向上看是逆邻接表。#defineMAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex; /该弧的尾和头顶点的位置该弧的尾和头顶点的位置 struct ArcBox * hlink, * tlink; /分别为弧头相同和弧尾相同的

14、弧的链域分别为弧头相同和弧尾相同的弧的链域 InfoType *info; /该弧相关信息的指针该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分别指向该顶点第一条入弧和出弧分别指向该顶点第一条入弧和出弧 VexNode;typedef struct VexNodexlistMAX_VERTEX_NUM; /表头向量表头向量 intvexnum, arcnum; /有向图的当前顶点数和弧数有向图的当前顶点数和弧数 OLGraph; （3）C语言描述语言描述（4）图形表

15、示）图形表示图图7.7有向图的十字链表有向图的十字链表V1 V2 (a)V3 V4 V1(b) 0 1V2 1 V3 2 V4 3 0 2 2 0 3 0 2 3 3 1 3 2 0 （5）图的构造）图的构造 Status CreateDG (OLGraph &G) /采用十字链表存储表示，构造有向图采用十字链表存储表示，构造有向图G(G.kind = DG)。scanf (&G.vexnum, &G.arcnum, &IncInfo);/IncInfo为为0则各弧不含其他信息则各弧不含其他信息for (i = 0; i G.vexnum; + + i) /构造表头向量构造表头向量 scanf

16、 (&G.xlisti.data);/输入顶点值输入顶点值 G.xlisti.firstin = NULL;/初始化指针初始化指针 G.xlisti.firstout = NULL;for (k = 0; k info);/若弧含有相关信息，则输入若弧含有相关信息，则输入 / for / CreateDG算法算法7.3如下：如下： 7.2.4 邻接多重表（无向图）邻接多重表（无向图）（1）定义）定义 邻接多重表（邻接多重表（Adjacency Multilist）：是无向图的另一种链式）：是无向图的另一种链式存储结构。邻接多重表的结构和十字链表类似。在邻接多重表中，存储结构。邻接多重表的结构和

17、十字链表类似。在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附两个所有依附于同一顶点的边串联在同一链表中，由于每条边依附两个顶点，则每个边结点同时链接在两个链表中。顶点，则每个边结点同时链接在两个链表中。（2）结点结构）结点结构边结点边结点mark ivex ilink jvex jlink infodata firstedge顶点结点顶点结点 边结点由边结点由6个域组成：个域组成：mark：标志域，用以标记该条边是否被搜索过。：标志域，用以标记该条边是否被搜索过。ivex和和jvex：为该边依附的两个顶点在图中的位置。：为该边依附的两个顶点在图中的位置。ilink：链域

18、，指向下一条依附于顶点：链域，指向下一条依附于顶点ivex的边。的边。jlink：链域，指向下一条依附于顶点：链域，指向下一条依附于顶点jvex的边。的边。info：数据域，指向和边相关的各种信息的指针域。：数据域，指向和边相关的各种信息的指针域。在邻接多重表中在邻接多重表中,每每一条边用一个结点一条边用一个结点表示表示,每一个顶点也每一个顶点也用一个结点表示。用一个结点表示。 顶点结点有顶点结点有2个域组成：个域组成： data：数据域，存储和该顶点相关的信息。：数据域，存储和该顶点相关的信息。 firstedge：链域，指示第一条依附于该顶点的边。：链域，指示第一条依附于该顶点的边。（4）

19、图形表示）图形表示G2V1 V2V4 V5V3图图7.8无向图无向图G2的邻接多重表的邻接多重表4V1 0 1V2 1 V3 2 V4 3 0 V5 0 3 2 1 2 3 4 1 2 4（3）C语言描述语言描述 #defineMAX_VERTEX_NUM 20typedef emnu unvisited, visited VisitIf;typedef struct EBox VisitIf mark;/访问标记访问标记 int ivex, jvex;/该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox * ilink, * jlink; /分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边 InfoType *info;/该边信息指针该边信息指针 EBox;typedef struct VexBox VertexType data; EBox * firstedge; /分别指向该顶点第一条入弧和出弧分别指向该顶点第一条入弧和出弧 VexBox;typedef struct VexBoxadjmulistMAX_VERTEX_NUM; intvexnum, edgenum;/无向图的当前顶点数和边数无向图的当前顶点数和边数 AMLGraph;26 结束语结束语