《数据结构》-图的存储结构

7.1图的定义和术语,7.2 图的存储结构,7.3 图的遍历,7.4 图的连通性问题,7.5 有向无环图及其应用,7.6 最短路径,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、无向图的邻接多重表存储表示,7.2 图的存储结构,7.2 图的存储结构,7.2.1 数组表示法（邻接矩阵）,（1）定义 数组表示法：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。,（2）C语言描述#defineINFINITY INT_MAX/最大值#defineMAX_VERTEX_NUM 20/最大顶点个数typedef enum DG, DN, UDG, UDN GraphKind;/有向图，有向网，无向图，无向网typedef struct ArcCell VRTypeadj;/ VRType是顶点关系类型。对无权图，用1/或0表示相邻否；对带权图，则为权值类型。 InfoType*info;/该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexTypevexsMAX_VERTEX_NUM;/顶点向量 AdjMatrixarcs;/邻接矩阵 intvexnum, arcnum;/图的当前顶点数和弧数 GraphKindkind;/图的种类标志 MGraph;,定义:矩阵的元素为,有向图的邻接矩阵为非对称矩阵,在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 行 1 的个数可得顶点 j 的入度。在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。,（3）邻接矩阵中顶点度的求法 对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和，即：,对于有向图，顶点vi的出度OD(vi)为第i行的元素之和，顶点vi的入度ID(vi)为第j列的元素之和。,（4）网的邻接矩阵,网的邻接矩阵可定义为：,例如，下图列出了一个有向网和它的邻接矩阵。,(b) 邻接矩阵,(a) 网N,（5）图的构造,算法7.1如下： Status CreateGraph (MGraph / CreateGraph,算法7.1是在邻接矩阵存储结构MGraph上对图的构造操作的实现框架，它根据图G的种类调用具体构造算法。,Status CreateUDN (MGraph / CreateUDN,算法7.2如下：,算法7.2构造一个具有n个顶点和e条边的无向网G。其时间复杂度为O(n2+e*n)，其中对邻接矩阵G.arcs的初始化耗费了O(n2)的时间。,7.2.2邻接表表示法(Adjacency List) 用邻接矩阵存储弧或边的信息，比较浪费空间，如果我们只存储图中已有的弧或边的信息，就可以节省空间。而图中所有顶点都是依附于某两个顶点的，因此如果对图中的所有顶点都建立一个单链表来存储所有依附于该顶点的弧或边，就可以把图中所有已有的弧或边的信息保存下来。而对于图中所有顶点还是使用一个一维数组来存放。这种存储方法就是邻接表表示法。 在邻接表表示法中，对于顶点单元i，需要存放的内容有顶点信息以及指向依附于该顶点的第一条弧或边的指针，用这个指针来指向依附于顶点i的所有的弧或边组成的单链表。对于弧单元，需要存放该弧指向的顶点的位置（也就是该弧依附的另一个顶点的位置）和指向依附于该弧的弧尾顶点的下一条弧的指针。对于弧和顶点分别可以用如下的结构实现：,7.2.2 邻接表,（1）定义,邻接表（Adjacency List）：是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。,逆邻接表：即对每个顶点vi建立一个链接以vi为头的弧的表。在逆邻接表中可以方便的确定顶点的入度或以顶点vi为头的弧。,（2）结点结构,表结点由3个域组成： adjvex：邻接点域，指示与顶点vi邻接的点在图中的位置。 nextarc：链域，指示下一条边或弧的结点。 info：数据域，存储和边或弧相关的信息，如权值等。,头结点由2个域组成： data：数据域，存储顶点vi的名或其他有关信息。 firstarc：链域，指向链表中第一个结点。,表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的链表。,#defineMAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针 InfoType *info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息 struct ArcNode * firstarc;/指向第一条依附该顶点的弧的指针 VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum;/图的当前顶点数和弧数 kind kind;/图的种类标志 ALGraph;,（3）C语言描述,（4）图形表示,(b) G1的邻接表,(c) G1的逆邻接表,(d) G2的邻接表图7.6 邻接表和逆邻接表,对于无向图，顶点vi的度恰为第i个链表中的结点数。对于有向图，顶点vi的出度OD(vi)为第i个链表中的结点个数；求顶点vi的 入度ID(vi)必须遍历整个邻接表，查找所有链表中其邻接点域的值为i的结点， 它们的总和即为顶点vi的入度。,（5）邻接表中顶点度的求法,在无向图的邻接表中，顶点Vi的度恰为第i个链表中的结点数。,有向图的邻接表,可见，在有向图的邻接表中不易找到指向该顶点的弧,有向图的逆邻接表,在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧,7.2.3 十字链表（有向图）,（1）定义 十字链表（Orthogonal List）：是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧头相同的弧在同以一链表上，弧尾相同的弧也在同一链表上,（2）结点结构,弧结点,头结点（顶点结点）,弧结点由5个域组成：tailvex：尾域，指示弧尾顶点在图中的位置。headvex：头域，指示弧头顶点在图中的位置。hlink：链域，指向弧头相同的下一条弧。tlink：链域，指向弧尾相同的下一条弧。info：数据域，指向该弧的相关信息。,头结点由3个域组成：data：数据域，存储和顶点相关的信息，如顶点名称等。firstin：链域，指向以该顶点为弧头的第一个弧结点。firstout：链域，指向以该顶点为弧尾的第一个弧结点。,三、有向图的十字链表存储表示,0 1 2,从横向上看是邻接表，从纵向上看是逆邻接表。,#defineMAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex; /该弧的尾和头顶点的位置 struct ArcBox * hlink, * tlink; /分别为弧头相同和弧尾相同的弧的链域 InfoType *info; /该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分别指向该顶点第一条入弧和出弧 VexNode;typedef struct VexNodexlistMAX_VERTEX_NUM; /表头向量 intvexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;,（3）C语言描述,（4）图形表示,图7.7有向图的十字链表,（5）图的构造,Status CreateDG (OLGraph /若弧含有相关信息，则输入 / for / CreateDG,算法7.3如下：,7.2.4 邻接多重表（无向图）,（1）定义 邻接多重表（Adjacency Multilist）：是无向图的另一种链式存储结构。邻接多重表的结构和十字链表类似。在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附两个顶点，则每个边结点同时链接在两个链表中。,（2）结点结构,边结点由6个域组成：mark：标志域，用以标记该条边是否被搜索过。ivex和jvex：为该边依附的两个顶点在图中的位置。ilink：链域，指向下一条依附于顶点ivex的边。jlink：链域，指向下一条依附于顶点jvex的边。info：数据域，指向和边相关的各种信息的指针域。,在邻接多重表中,每一条边用一个结点表示,每一个顶点也用一个结点表示。,顶点结点有2个域组成： data：数据域，存储和该顶点相关的信息。 firstedge：链域，指示第一条依附于该顶点的边。,（4）图形表示,图7.8无向图G2的邻接多重表,（3）C语言描述,#defineMAX_VERTEX_NUM 20typedef emnu unvisited, visited VisitIf;typedef struct EBox VisitIf mark;/访问标记 int ivex, jvex;/该边依附的两个顶点的位置 struct EBox * ilink, * jlink; /分别指向依附这两个