数据结构

2024-07-17 17:04| 来源: 网络整理| 查看: 265

图

图（Graph）是由莱昂哈德·欧拉1在1736年首先引进的一类很重要的非线性结构，可称为图形结构或网状结构。图的应用领域非常广泛，例如：电路分析、工程规划、化合物分类、统计力学、自动化、语言学等。

一、图的定义

图G由两个集合V、E构成，V是节点的有限非空集合,E是节点的二元组集合，节点二元组称为边。V(G)和E(G)分别称为图G的节点集（顶点集）与边集，也可用G=(V,E)表示图。

线性表、树、图的差异

在线性表中数据元素叫元素，在树中将数据元素叫结点，在图中数据元素称之为顶点（Vertex）。线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。二、图的分类无向图若顶点 Vi 到 Vj 之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(Vi ,Vj)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected Graphs），例如图2-1所示：

图 2-1 无向图

可看出图2-1中的顶点集和边集如下：

顶点集：V1={A,B,C,D}边集：E1={(A,B),(B,C),(A,C),(A,D)} 有向图若从顶点Vi 到 Vj 的边有方向，则称这条边为有向边，也称为弧（Arc）。一般采用尖括号括起来表示，例如。前者Vi称为弧尾（Tail），后者Vj称为弧头（Head）。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs），例如图2-2所示：

图 2-2 有向图

其顶点集V和弧集E如下：

顶点集：V2={A,B,C,D}弧集：E2={,,,} 无向完全图在一个具有n个顶点的无向图中，倘若每个顶点与其他n-1个顶点之间都有边相连，则会有n(n-1)/2条边，这是具有n个顶点的无向图可能的最大边数。一个具有n(n-1)/2条边的n个顶点的无向图被称为无向完全图。例如图2-3所示：

图 2-3 无向完全图有向完全图在一个具有n顶点的有向图中，最多可能有n(n-1)条弧，具有n(n-1)条弧的n个顶点的有向图称为完全有向图，例如图2-4所示：

图 2-3 无向完全图子图对于图2-4中，右侧灰色部分均为前者的子图。

图 2-4 无向完全图带权图在带权图中每条边都有相应的权重，称为边权值，它可以用来表示结点之间的距离或者两结点“走动”的代价，加权图又被称为网络，如图2-5所示

图 2-5 带权图三、图的基本术语邻接若（V1，V2）是E(G)中的一条边，则称顶点V1和V2是相邻接（Adjacent）的顶点，称边（V1，V2）是依附于顶点V1和V2的边；路径顶点Vi到顶点Vj之间的连线称为路径（Path）；简单路径在一条路径中，如果除了第一个顶点和最后一个顶点外，其余顶点各不相同，则称这样的路径为简单路径；回路（环）若一条路径的起点和终点相同（即Vi=Vj），则称此路径为回路或者环；简单回路（简单环）在一个图的序列中除过第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路或者简单环；顶点的度顶点的度是指依附于某顶点Vi的边数，通常记为TD(Vi)；顶点的入度（InDegree）是指以Vi为终点的弧的而数目，记为ID(Vi)；顶点的出度（OutDegree）是指以Vi为始点的弧的数目，记为OD(Vi)；于是有：TD(Vi) = ID(Vi)+OD(Vi)联通若从顶点Vi到顶点Vj（ i ≠ j ）有路径，则Vi和Vj是联通的；连通图在无向图中，任意两个顶点Vi和Vj都是联通的则称这样的无向图为连通图；强连通图在有向图中，任意一对顶点Vi和Vj（ i ≠ j ）均有从Vi到Vj和从Vj到Vi的有向路径，则称为强连通图。四、图的存储结构邻接矩阵（Adjacency Matrex）存储法图的邻接矩阵存储方式是使用两个数组来表示图，其中一个是一维数组，用来保存图中的各个顶点信息，另一个是二维数组（成为邻接矩阵），用来存储图中的边或弧的信息。

图2-1所示无向图使用邻接矩阵存储如下：

无向图使用邻接矩阵

图 4-1 无向图邻接矩阵

图2-2所示有向图使用邻接矩阵存储如下：

有向图使用邻接矩阵

图 4-2 有向图邻接矩阵

注：在邻接矩阵中，使用0表示两个顶点之间不相连，使用1表示两个顶点之间相连；

邻接表（Adjacency Lists）存储法图的邻接表存储结构是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是数组，另一部分是链表，数组用来每条单链表的表头，有数组的特性可知定位每条单链表的时间都是O(1)。

图2-1所示无向图使用邻接表存储如下：

图 4-3 无向图邻接表存储

图2-2所示有向图使用邻接表存储如下：

图 4-4 有向图邻接表存储逆邻接表在一个邻接表中，可以很轻易的得出每个结点的出度，但是，若想得到该系欸但的入度，则需要遍历整个链表。为了方便节点入度的确定，可以建立有向图的逆邻接表，逆邻接表的建立和邻接表正好相反。

图2-2所示有向图使用邻接表存储如下：

图 4-5 有向图逆邻接表存储十字链表十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。

逆邻接表存储结构

图 4-6 十字链表存储顶点结构

其中FirstIn用来表示入边表头指针，指向该顶点的入边表中的第一个结点，FirstOut表示出边表头指针，指向该顶点的出边表的第一个结点。

边表结点结构

图 4-7 十字链表存储边表结点结构

其中 tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink 是指入边表指针域，指向终点相同的下一条边，taillink 是指边表指针域，指向起点相同的下一条边。

图 4-8 有向图

根据上图4-8所示有向图可得十字链表存储如下图4-8所示：

图 4-9 有向图十字链表存储

在图 4-8 中对于顶点 A 来说，它存在顶点 B 的入边，因此 A 的 FirstIn 应该指向顶点 B 的边表结点中的 headvex 为 A 的结点，如上图 4-9 中的 ①，对于顶点 B 有来自顶点 C 的入边，因此 B 的 FirstIn 应该指向顶点 C 的边表结点中 headvex 为 B 的结点，如图 4-9 中的 ②，以此类推便可得到十字链表的存储方式图。

邻接多重表十字链表主要用来解决有向图的存储结构优化问题，对于无向图的操作如果关注重点是每个顶点，那么采用邻接表存储是一个不错的选择，但是，如果想要对其中某些边进行标记或者删除等操作时，在邻接表中需要分别找到这条边的两个边表结点进行操作，显然是比较麻烦的，所以便有了邻接多重表。

首先需要重新定义新的边表结点结构如下图 4-10所示：

在这里插入图片描述