图的存储结构课件

1、图的存储结构课件7.1图的定义和术语图的定义和术语 7.2 图的存储结构图的存储结构 7.3 图的遍历图的遍历 7.4 图的连通性问题图的连通性问题7.5 有向无环图及其应用有向无环图及其应用7.6 最短路径最短路径图的存储结构课件一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示7.2 图的存储结构图的存储结构 图的存储结构课件7.2 图的存储结构图的存储结构7.2.1 数组表示法（邻接矩阵）数组表示法（邻接矩阵） （1）定义）定义 数组表示法：用两个数组分别存储数据元素（顶点）的信数组表示法：用两个数组分别存储数据元素（顶

2、点）的信息和数据元素之间的关系（边或弧）的信息。息和数据元素之间的关系（边或弧）的信息。 （2）C语言描述语言描述#defineINFINITY INT_MAX/最大值最大值#defineMAX_VERTEX_NUM 20/最大顶点个数最大顶点个数typedef enum DG, DN, UDG, UDN GraphKind;/有向图，有向网，无向图，无向网有向图，有向网，无向图，无向网typedef struct ArcCell VRTypeadj;/ VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用1/或或0表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为

3、权值类型。 InfoType*info;/该弧相关信息的指针该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexTypevexsMAX_VERTEX_NUM;/顶点向量顶点向量 AdjMatrixarcs;/邻接矩阵邻接矩阵 intvexnum, arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 GraphKindkind;/图的种类标志图的种类标志 MGraph;图的存储结构课件Aij=0 (i,j)VR1 (i,j)VRBACDFE定义定义:矩阵的元素为矩阵的元素为0 1 0

4、0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 图的存储结构课件有向图的邻接矩阵有向图的邻接矩阵为非对称矩阵为非对称矩阵ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0图的存储结构课件图的存储结构课件（3）邻接矩阵中顶点度的求法）邻接矩阵中顶点度的求法 对于无向图，顶点对于无向图，顶点vi的度是邻接矩阵中第的度是邻接矩阵中第i行（或第行（或第i列）的列）的元素之和，即：元素之和，即：10)_()(njiNUMVERTEXMAXnjiAvTD 对于有向图，顶点对

5、于有向图，顶点vi的出度的出度OD(vi)为第为第i行的元素之和，顶行的元素之和，顶点点vi的入度的入度ID(vi)为第为第j列的元素之和。列的元素之和。（4）网的邻接矩阵）网的邻接矩阵网的邻接矩阵可定义为：网的邻接矩阵可定义为： wi,j若若或或(vi, vj) VRAij = 反之反之例如，下图列出了一个有向网和它的邻接矩阵。例如，下图列出了一个有向网和它的邻接矩阵。 1356598475 (b) 邻接矩阵邻接矩阵(a) 网网N45387 9 1 655 V1 V2 V6 V3V5V4图的存储结构课件（5）图的构造）图的构造算法算法7.1如下：如下： Status CreateGraph

6、(MGraph &G) /采用数组（邻接矩阵）表示法，构造图采用数组（邻接矩阵）表示法，构造图G。scanf (&G.kind);switch (G.kind) case DG:return CreateDG;/构造有向图构造有向图G case DN:return CreateDN;/构造有向网构造有向网G case UDG:return CreateUDG;/构造无向图构造无向图G case UDG:return CreateUDG;/构造无向网构造无向网G default:return ERROR; / CreateGraph算法算法7.1是在邻接矩阵存储结构是在邻接矩阵存储结构MGrap

7、h上对图的构造操上对图的构造操作的实现框架，它根据图作的实现框架，它根据图G的种类调用具体构造算法。的种类调用具体构造算法。图的存储结构课件 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 G.vexnum; + + i)/

8、初始化邻接矩阵初始化邻接矩阵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.);/若弧

9、含有相关信息，则输入若弧含有相关信息，则输入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) 用邻接矩阵存储弧或边的信息，比较浪费空间，如果我们只存储图中已有的弧或边的信息，就可以节省空间。

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

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

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

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

14、 firstarc;/指向第一条依附该顶点的弧的指针指向第一条依附该顶点的弧的指针 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 30V1V

15、2V3V40 1 2 3 2003(c) G1的逆邻接表的逆邻接表图的存储结构课件 (d) G2的邻接表的邻接表图图7.6 邻接表和逆邻接表邻接表和逆邻接表对于无向图，顶点对于无向图，顶点vi的度恰为第的度恰为第i个链表中的结点数。个链表中的结点数。对于有向图，顶点对于有向图，顶点vi的出度的出度OD(vi)为第为第i个链表中的结点个数；求顶点个链表中的结点个数；求顶点vi的的 入度入度ID(vi)必须遍历整个邻接表，查找所有链表中其邻接点域的值为必须遍历整个邻接表，查找所有链表中其邻接点域的值为i的结点，的结点， 它们的总和即为顶点它们的总和即为顶点vi的入度。的入度。（5）邻接表中顶点度的

16、求法）邻接表中顶点度的求法V1V2V3V40 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

17、 01234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧图的存储结构课件7.2.3 十字链表（有向图）十字链表（有向图）（1）定义）定义 十字链表（十字链表（Orthogonal List）：是有向图的另一种链式存储结构。可）：是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧头相同的弧在同以一链表上，弧尾相同的弧也在同一链表上头相同的弧在同以一链表上，弧尾相同的弧也在同一链表上 （2）结点结构）结点结构弧结点弧结点头结点（顶点结点）头结点（顶点结点）data firstin

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

19、据域，存储和顶点相关的信息，如顶点名称等。firstin：链域，指向以该顶点为弧头的第一个弧结点。：链域，指向以该顶点为弧头的第一个弧结点。firstout：链域，指向以该顶点为弧尾的第一个弧结点。：链域，指向以该顶点为弧尾的第一个弧结点。图的存储结构课件三、有向图的十字链表存储表示三、有向图的十字链表存储表示 ABCABC0 1 20 2 0 12 1 2 0 从横向上看是邻接表，从纵从横向上看是邻接表，从纵向上看是逆邻接表。向上看是逆邻接表。图的存储结构课件#defineMAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex;

20、 /该弧的尾和头顶点的位置该弧的尾和头顶点的位置 struct ArcBox * hlink, * tlink; /分别为弧头相同和弧尾相同的弧的链域分别为弧头相同和弧尾相同的弧的链域 InfoType *info; /该弧相关信息的指针该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分别指向该顶点第一条入弧和出弧分别指向该顶点第一条入弧和出弧 VexNode;typedef struct VexNodexlistMAX_VERTEX_NUM; /表头向量表头向量 i

21、ntvexnum, arcnum; /有向图的当前顶点数和弧数有向图的当前顶点数和弧数 OLGraph; （3）C语言描述语言描述图的存储结构课件（4）图形表示）图形表示图图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, &I

22、ncInfo);/IncInfo为为0则各弧不含其他信息则各弧不含其他信息for (i = 0; i G.vexnum; + + i) /构造表头向量构造表头向量 scanf (&G.xlisti.data);/输入顶点值输入顶点值 G.xlisti.firstin = NULL;/初始化指针初始化指针 G.xlisti.firstout = NULL;for (k = 0; k info);/若弧含有相关信息，则输入若弧含有相关信息，则输入 / for / CreateDG算法算法7.3如下：如下： 图的存储结构课件7.2.4 邻接多重表（无向图）邻接多重表（无向图）（1）定义）定义 邻接多

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