数据结构和算法：图

蔚落 2022-07-13 09:45 190阅读 0赞

图（Graph）是一种较树更为复杂的非线性数据结构。在树形结构中，数据元素之间的关系是层次型的，树中除叶子以外的每一个数据元素可以和它下一层的多个数据元素存在关系；但除根元素以外的每一个数据元素只能且必须和它上一层中的一个数据元素存在关系。而在图形结构中，数据元素之间的关系是任意的，图中每一个数据元素可以和任何其它数据元素相关联。

# 图的基本概念 #

# 图的术语 #

1．完全图(complete graph)：在有n个顶点的无向图中，若有 n(n-1)／2条边，则称此无向图为完全无向图。在有n个顶点的有向图中，若有n(n-1)条边，则称此图为完全有向图。在完全图中边（弧）数目达到最大。

2．权(weight)：在某些图的应用中，边（弧）上具有与它相关的系数，称之为权。这些权可以表示从一个顶点到另一个顶点的距离、花费的代价、所需的时间、次数等。这种带权图也被称为网络(network)。

3．邻接点(adjacent vertex)：如果(v，w)是无向图G中的一条边，则称v与w互为邻接顶点，且边(v，w)称为依附于顶点v和w。如果＜v、w＞是有向图G 中的一条弧，则称顶点v邻接到顶点w（也称v是w的前驱），顶点w邻接自顶点v（也称w是v的后继），弧＜v，w＞与顶点v与w相关联。

4．子图(subgraph)

5．顶点的度(degree)：在无向图中，一个顶点v的度是依附于顶点v的边的条数，记作TD(v)。在有向图中，以顶点v为始点的有向边的条数称为顶点v的出度，记作OD(v)；以顶点v为终点的有向边的条数称为顶点v的入度，记作ID(v)。有向图中顶点v的度等于该顶点的入度与出度之和：TD(v)＝ID(v)十OD(v)。

6．路径(path)：在图G＝(V，E)中，若从顶点vi出发，沿一些边（或弧）经过一些顶点vp1、vp2、…、vpk，到达顶点vj，则顶点序列(vi、vp1、vp2、…、 vpk、vj )被称为从顶点vi到顶点vj的路径。

7．路径长度(path length)：对于不带权的图，路径长度是指此路径上边的数目。对于带权图，路径长度是指路径上各边的权之和。

8．简单路径与回路(cycle)：对于一路径（v1、v2、…、vm），若路径上各顶点均不相同，则称这路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm相同，则称这样的路径为回路或环。

9．连通图与连通分量：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi与vj是连通的。如果无向图中任意两个顶点都是连通的，则称此无向图是连通图。非连通图的极大连通子图（包括所有连通的顶点和这些顶点依附的所有的边）叫做连通分量。

如下图（a）所示是一个非连通图，图（b）所示是相应的三个连通分量。

![图][SouthEast]

10．强连通图与强连通分量(strongly connected digraph)：在有向图中，若对于顶点vi和vj，存在一条从vi到vj和从vj到vi的路径，则称顶点vi和顶点vj是强连通。如果有向图中任意两个顶点都是强连通的，则称此有向图为强连通图。非强连通图的极大强连通子图叫做强连通分量。

11．生成树(spanning tree)：一个连通图的生成树是它的极小连通子图，它包含图中全部n个顶点和仅使这n个顶点连通的n-1条边。如果一个有向图只有一个入度为零的顶点，且其它顶点的入度均为1，则称这个有向图为有向树。一个有向图的生成森林由若干棵有向树组成，生成森林含有图中所有的顶点，且只有足以构成若干棵互不相交的有向树的弧。

# 图的存储结构 #

由于在图中，任何两个顶点之间都可能存在联系，所以无法在存储位置上反映数据元素之间的联系，因此图没有顺序存贮结构。按图中顶点之间的联系，图的存储结构似乎采用多重链表表示比较恰当。但是若采用多重链表，则链表中结点的结构难以确定。因为结点中的指针数若按顶点度的最大值来设置，则会浪费空间，因为有很多顶点的度小于最大值；若顶点的指针数按每个顶点的度数来设置，则存储结构中会有很多顶点的结构不一致，给图的运算带来困难。因此，图的存储结构不宜采用多重链表。

图的存贮结构应根据具体问题的要求来设计。常用的存贮结构有邻接矩阵、邻接表、邻接多重表和十字链表。

## **邻接矩阵** ##

在图的邻接矩阵表示中，除了记录每一个顶点信息的顶点表外，还有一个表示各个顶点之间关系的矩阵，称之为邻接矩阵。若设图G＝(V，E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组Arcs\[n\]\[n\]，它的定义为：

![邻接矩阵][SouthEast 1]

对于网络(或带权图)，邻接矩阵定义如下：

![邻接矩阵][SouthEast 2]

下图给出了无向图、有向图和有向网的邻接矩阵。其中一维数组Vertexes\[\]用于存储顶点的信息，二维数组Arcs\[\]\[\]用于存储边（或弧）的信息。

![邻接矩阵][SouthEast 3]

邻接矩阵是指用矩阵来表示图。它是采用矩阵来描述图中顶点之间的关系(及弧或边的权)。  
假设图中顶点数为n，则邻接矩阵定义为：

![04.jpg_raw_true_3691463][]

下面通过示意图来进行解释。

![05.jpg_raw_true_3691463][]

图中的G1是无向图和它对应的邻接矩阵

![06.jpg_raw_true_3691463][]

图中的G2是无向图和它对应的邻接矩阵。

通常采用两个数组来实现邻接矩阵：一个一维数组用来保存顶点信息，一个二维数组来用保存边的信息。 邻接矩阵的缺点就是比较耗费空间。

## **稀疏矩阵** ##

## **邻接表** ##

邻接表是邻接矩阵的改进。它把邻接矩阵的每一行改为一个单链表。

对于无向图，把依附于同一个顶点的边链接在同一个单链表中称为边链表，边链表中的每一个结点代表一条边叫做边结点。在边结点中保存着与该边相关联的另一顶点的序号和指向同一链表中下一个边结点的指针；

对于有向图，把从同一个顶点发出的弧链接在同一个单链表中称为弧链表，弧链表的每一个结点代表一条弧叫做弧结点，在弧结点中保存着该弧的弧头顶点序号和指向同一链表中下一个弧结点的指针。如果是带权图，则在边（弧）结点中还要保存该边（或弧）上的权值。

在邻接表中，对于图中的每一个顶点也用一个结点表示，称为顶点结点。顶点结点中保存了该顶点的信息和指向该顶点相应的边（弧）链表的指针。所有的顶点结点用顺序表存储，并假设顶点的序号为数组的下标。

下图给出了无向图的邻接表表示。从无向图的邻接表中可以看到，同一条边在邻接表中出现了两次，这是因为(vi，vj)与(vj，vi)虽是同一条边，但在邻接表中，(vi，vj)对应的边结点在顶点vi的边链表中；(vj，vi) 对应的边结点在顶点vj的边链表中。如果想知道顶点vi的度，只需统计顶点vi的边链表中边结点的个数即可。

![邻接表][SouthEast 4]

邻接表是图的一种链式存储表示方法。它是改进后的”邻接矩阵”，它的缺点是不方便判断两个顶点之间是否有边，但是相对邻接矩阵来说更省空间。

![07.jpg_raw_true_3691463][]

图中的G1是无向图和它对应的邻接矩阵。

![08.jpg_raw_true_3691463][]

图中的G2是无向图和它对应的邻接矩阵。

## **双链式存储结构** ##

## **邻接多重表** ##

在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成。其中，tag是标记域，标记该边是否被处理或被搜索过；wieght为边的信息域，用于存储边的权值；adjvex1和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；nextarc1域是链接指针，指向下一条依附于顶点adjvex1的边；nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。对图中的每一个顶点用一个顶点结点表示，它有两个域组成。其中，data域存储有关顶点的信息；firstarc域是链接指针，指向第一条依附于该顶点的边。所有的顶点结点组成一个顺序表。

下图所示，给出了无向图的邻接多重表表示，及其两种结点的示例。在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。

![SouthEast 5][]

## 十字链表 ##

在有向图的十字链表中，图中的每一条弧用一个弧结点表示。弧结点的结构与无向图邻接多重表中的边结点结构类似，也有六个域。其中，tag是标记域，标记该弧是否被处理或被搜索过；wieght为弧的信息域，用于存储弧的权值等信息；tailvex和headvex是分别表示弧尾顶点序号和弧头顶点序号的顶点域；tailnextarc域是链接指针，指向下一条以顶点tailvex为始点（弧尾）的弧；headnextarc也是链接指针，指向下一条以顶点headvex为终点（弧头）的弧。对有向图中的每一个顶点也用一个顶点结点表示，它由三个域组成。其中，data域存储有关顶点的信息；firstinarc域是链接指针，指向第一条以该顶点为终点的弧；firstoutarc域也是链接指针，指向第一条以该顶点为始点的弧。所有的顶点结点组成一个顺序表。

下图给出了有向图十字链表表示示例及其顶点结点和弧结点的结构

![SouthEast 6][]

# 图的遍历与连通性 #

对于给定的图，沿着一些边（或弧）访问图中所有的顶点，且使每个顶点仅被访问一次，这个过程叫做图的遍历。

图的遍历通常有两种方法：深度优先遍历(Depth First Traversal)和广度优先遍历(Breadth First Traversal)。这两种方法对无向图和有向图都是适用的，但在下面的讨论中将主要介绍对无向图的遍历。

## 深度优先遍历 ##

图的深度优先遍历基于深度优先搜索DFS(Depth First Search)，深度优先搜索是从图中某一顶点v出发，在访问顶点v后，再依次从v的任一还没有被访问的邻接顶点w出发进行深度优先搜索，直到图中所有与顶点v由路径相通的顶点都被访问过为止。这是一个递归定义，所以图的深度优先搜索可以用递归算法实现。

下图（a）给出了深度优先搜索的示例。由于该图是连通的，所以从顶点A出发，通过一次深度优先搜索，就可以访问图中的所有顶点。图的深度优先搜索的访问顺序与树的前序遍历顺序类似。图 (b)给出了在深度优先搜索的过程中，访问的所有顶点和经过的边，图中各顶点旁附加的数字表示各顶点被访问的次序。在图 (b)中，共有n-1条边连结了所有n个顶点，在此把它称为图（a）的深度优先搜索生成树。

![SouthEast 7][]

## 广度优先遍历 ##

图的广度优先遍历基于广度优先搜索BFS (Breadth First Search)，广度优先搜索是从图中某一顶点v出发，在访问顶点v后再访问v的各个未曾被访问过的邻接顶点w1、w2、…、wk，然后再依次访问w1、w2、…、wk的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，……，如此下去，直到图中所有和顶点v由路径连通的顶点都被访问到为止。

## 连通分量 ##

对于连通图，从任一顶点出发，只需一次调用深度优先搜索算法或广度优先搜索算法就可以访问到图中的所有顶点；对于非连通图时，从图中某一顶点出发，一次调用深度优先搜索算法或广度优先搜索算法不可能访问到图中的所有顶点，只能访问到该顶点所在的极大连通子图(即连通分量)的所有顶点。非连通图有n个连通分量，就要n次调用DFS或BFS才能访问图中的所有顶点。若从图的每一个连通分量中的一个顶点出发进行搜索，就可以求得图的所有连通分量。所谓连通分量是指非连通图中极大连通子图。

## 最小生成树 ##

一个连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点和使n个顶点连通的n-1条边。这意味着对于生成树来说，若删除它的一条边，就会使生成树变成非连通图；若给它增加一条边，就会形成图中的一个回路。另一方面，一个连通图的生成树不是唯一的，使用不同的方法遍历图，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树；而且生成树有时还和图的存储结构中具体的结点顺序有关。

对于一个带权的连通图(即网络)，如何找出一棵生成树，使得各边上的权值总和达到最小，这是一个有实际意义的问题。

对于这样一个有n个顶点的网络，可以有不同的生成树，每一棵生成树都可以构成通信网络。我们希望能够根据各条边上的权值，选择一棵总造价最小的生成树，这就是构造网络的最小(代价)生成树(Minimum-cost Spanning Tree)问题。

![SouthEast 8][]

# 克鲁斯卡尔算法 #

克鲁斯卡尔(Kruskal)算法的基本思想是：设一个有n个顶点的连通网络G＝\{V，E\}，最初先构造一个包括全部n个顶点和0条边的森林F＝\{T0、T1、…、Tn-1\}，以后每一步向F中加入一条边（v、u），该边应当是所依附的两个顶点v和u分别在森林F的两棵不同的树上的所有边中具有最小权值的边。由于这条边的加入，使F中的某两棵树合并为一棵，树的棵数减一。如此，经过n-1步，最终得到一棵有n-1条边且各边权值总和达到最小的生成树——最小生成树。

# 普里姆算法 #

# 最短路径 #

利用带权的图也可以表示n个城市之间的交通运输网络。此时图中的每一个顶点用于表示一个城市，图中的每一条边用于表示两个城市之间的直接交通运输路线，每条边上所附的权值可以表示该路线的长度或沿此路线运输所花费的时间或运费等。从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条（也就是说两个城市之间的通路可能有多条），但人们往往比较关心的是如何找到从一个城市到另一个城市花费最少的一条路径，也就是说要寻找带权有向图中两个顶点之间路径长度最短的路径。这个问题就是所谓的最短路径问题。本节将讨论最常见的三种求解最短路径的方法。

## 弧上权值为非负情形的单源点最短路径问题 ##

所谓弧上权值为非负情形的单源点最短路径问题就是对于给定一个带权有向图G（G中所有弧上的权均为非负值）与源点v，求从v到G中其余各顶点的最短路径。  
如下图所示的带权有向图。设源点为A，则源点A到其余顶点的最短路径分别为：（A、B）路径长度为10，（A、D、C）路径长度为50，（A、D）路径长度为30，（A、D、C、E）路径长度为60。

![SouthEast 9][]

## 迪杰斯特拉算法 ##

迪杰斯特拉(Dijkstra)提出了按路径长度的递增次序，逐条产生最短路径的方法。首先求出从源点v0到其余各顶点中长度最短的一条，然后参照它求出长度次短的一条最短路径，依次类推，直到从源点v0到其余各顶点的最短路径全部求出为止。

具体做法是：设集合S存放已经求出的最短路径的终点，初始状态时，集合S中只有一个源点v0（S=\{v0\}）。以后每求得一条最短路径(v0，…，vk)，就将vk加入到集合S中，直到全部顶点都加入到集合S中，算法就可以结束了。

右图给出了按照迪杰斯特拉算法对前图所示带权有向图逐步求最短路径的过程。

![SouthEast 10][]

# 贝尔曼—福特算法 #

# 弗洛伊德算法 #

# 拓扑排序算法 #

[SouthEast]: /images/20220713/836d5b036c264a4fa766e18d8b5f7cd8.png
[SouthEast 1]: /images/20220713/3f7907757d0a4e879dd7bad923c04f0a.png
[SouthEast 2]: /images/20220713/49928d211c31418d8fbfe6a7a076c5fe.png
[SouthEast 3]: /images/20220713/563eed13d27f4cebbf546236d87c12e4.png
[04.jpg_raw_true_3691463]: /images/20220713/7f331e7eba6943e081e4fc0e43367fc1.png
[05.jpg_raw_true_3691463]: /images/20220713/29e4a191d4454b619f932f5d2cb3c0cd.png
[06.jpg_raw_true_3691463]: /images/20220713/5ab5a16f699c4c3bbaf7245ffe85a254.png
[SouthEast 4]: /images/20220713/ec758f5b8e7b4037b8b372204b3793cf.png
[07.jpg_raw_true_3691463]: /images/20220713/4be4593b191a438097ac376b7b17bcad.png
[08.jpg_raw_true_3691463]: /images/20220713/f11ee41bf4214056b302cb1a7efaef4b.png
[SouthEast 5]: /images/20220713/25c15403d09946508392d19bb1c7e2a1.png
[SouthEast 6]: /images/20220713/562671ef0ed2494fa8823576782852f7.png
[SouthEast 7]: /images/20220713/14132d10122346ed9c945bf678b119f9.png
[SouthEast 8]: /images/20220713/fd979c305b12405c8c1f809295b53959.png
[SouthEast 9]: /images/20220713/7252dec82bae42ddb1dc24bff0c6ed0e.png
[SouthEast 10]: /images/20220713/c726dc66e3534c1581180cdfecb2879a.png