数据结构：图

简介

• 有向图：若E是有向边（也称为弧）的有限集合时，则称为G为有向图
• 无向图：若E是无向边（简称边）的有限集合时，则图G为无向图
• 完全图：在无向图中，如果任意两个顶点之间都存在边，则称为该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称为该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条有向边。
• 连通、连通图、连通分量：在无向图中，若从顶点v到顶点w有路径存在，则称为v和w是连通的。若图G中任意两个顶点都是连通的，则称为图G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。
• 强连通图、强连通分量：在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。
• 生成树、生成森林：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。对于生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会变成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。
• 顶点的度、入度和出度：图中每个顶点的度定义为以该顶点为一端的变的数据。无向图的全部顶点的度之和等于边数的两倍；有向图的全部顶点的入读和出度之和相等并且等于边数。
• 路径、路径长度和回路：路径上边的数据称为路径的长度。第一个顶点和最后一个顶点相同的路径称为回路或环。如果一个图有n个顶点，并且有大于n-1条边，则图一定有环。

线性表可以是空表，树可以是空树，但图不可以是空图

图的存储

无论是有向图还是无向图，主要的存储方式都有两种：邻接矩阵和邻接表。前者图的数据顺序存储结构，后者属于图的链接存储结构。

邻接矩阵法

所谓邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）。

• 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0或1的枚举类型
• 邻接矩阵表示法的空间复杂度为O(n²)，其中n为图中顶点数|V|
• 无向邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需要存储上（或下）三角矩阵的元素即可
• 对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度；对于有向图，邻接矩阵的第i行（或第i列）非0元素的个数正好是第i个顶点的出度（或入度）
• 用邻接矩阵发存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性
• 稠密图适合用邻接矩阵的存储表示

邻接表法

• 在邻接表中，给定一顶点，能很容易找到它的所有临边
• 如果G为无向图，则需要存储空间为O(|V|+2|E|)；如果G为有向图，则需要存储空间为O(|V|+|E|)
• 在有向图的邻接表中，求一个给定顶点的出度只需要计算其邻接表中的结点个数即可，但求顶点的入度，则需要遍历全部的邻接表
• 对于稀疏图，采用邻接表表示将极大节省存储空间
• 图的邻接表表示并不唯一

十字链表

十字链表是有向图的一种链式存储结构。

图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。

邻接多重表

邻接多重表是无向图的另一种链式存储结构。

图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。

图的遍历主要分为两种算法：广度优先搜索和深度优先搜索

广度优先搜索（BFS）

为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

假设从a结点开始访问，a先入队，此时队列非空，取出队头元素a，由于b、c与a邻接且未被访问过，于是依次访问b、c，并将b、c依次入队。队列非空，取出队头元素b，依次访问与b邻接且未被访问的顶点d、e，并将d、e入队(注意: a与b也邻接，但a已置访问标记，故不再重复访问)。此时队列非空，取出队头元素c，访问与c邻接且未被访问的顶点f、g，并将f、g入队。此时，取出队头元素d，但与d邻接且未被访问的顶点为空，故而不进行任何操作。继续取出队头元素e，将h入队列....当最后取出队头元素h后，队列为空，从而循环自动跳出。遍历结果为abcdefgh。

BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下（一个横排），空间复杂度为O(|V|)

• 当采用邻接矩阵存储方式时，查找每个顶点的邻接点所需要的时间为O(|V|)，故算法总的时间复杂度为O(|V|²)。
• 当采用邻接表存储时，每个顶点均需搜索一次，故时间复杂度为O(|V|)，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，算法的总时间复杂度为O(|V|+|E|)。

广度优先生成树

在广度遍历的过程中（有向图&无向图），我们可以得到一颗遍历树，称为广度优先生成树。需要注意的是，一给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。

深度优先搜索（DFS）

深度优先搜索（DFS）类似于树的先序遍历。

首先访问a，并置a已访间标记；然后访问与a邻接且未被访问的顶点b，置b已访问标记；然后访问与b邻接且未被访问的顶点d，置d已访问标记。此时d已没有未被访问过的邻接点，故返回上一个访问过的顶点b，访问与其邻接且未被访问的顶点e，置e访问标......依次类推，直到图中所有的顶点访问-次且仅访问次。遍历结 果为abdehcfe。

DFS算法是一个递归算法，需要借助一个递归工作栈，最坏情况下（一个竖排），它的空间复杂度为O(|V|)。

• 当采用邻接矩阵存储时，查找每个顶点的邻接点所需要的时间为O(|V|)，故算法总的时间复杂度为O(|V|²)。
• 当采用邻接表存储时，查找所有顶点的邻接点所需要的时间为O(|E|)，访问顶点所需要时间为O(|V|)，此时，算法的总时间复杂度为O(|V|+|E|)。

深度优先生成树

对于连通图调用DFS才可以产生深度优先生成树（有向图&无向图），否则产生的将是深度优先生成森林。和BFS类似，基于邻接表存储产生的深度优先生成树是不唯一的。

对于同一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

图的应用

图的应用主要包括：最小生成（代价）树、最短路径、拓扑排序和关键路径。

最小生成树

一个连通图的生成树是图的极小连通子图，它包含图中的所有顶点，并且只含尽可能少的边。这意味着对于生成树来说，若砍去它的一条边，就会使生成树变成非连通图若给它增加一条边，就会形成图中的一条回路。

假设G=(V， E)是一个带权连通无向图，U是顶点集V的一个空子集。

• 最小生成树不是唯一的，即最小生成树的树形不唯一
• 最小生成树的边的权值之和总是唯一的
• 最小生成树的边数等于顶点数减1

1. 普里姆算法

Prim算法的时间复杂度为O(|V|²)，不依赖|E|，因此它适用于求解边稠密的图的最小生成树。

2. 克鲁斯卡尔算法

与普里姆算法从顶点开始扩展最小生成树不同，克鲁斯卡尔算法是一种按照权值的递增次序选择合适的边来构造最小生成树的方法。

通常在克鲁斯卡尔算法中，采用堆来存放边的集合，则每次选择最小权值的边只需要O(log₂|E|)的时间。又生成树T中所有边可以看做一个等价类，每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述T，从而构造T的时间复杂度为O(|E|log₂|E|) ，因此克鲁斯卡尔算法适合边稀疏而顶点多的图。

最短路径

带权有向图G的最短路径问题，一般可分为两类：一是单源最短路径，即求图中某一个顶点到其他顶点的最短路径，可通过经典的Dijkstra算法求解；二是求每一对顶点间的最短路径，可通过Floyd-Warshall算法求解。

1. 迪杰斯特拉-单源最短路径

求带权有向图中某个源点到其余各顶点的最短路径，最常用的是Dijkstra算法。`如下图，从顶点1开始出发，求其到其余顶点的最短路径。

若使用邻接矩阵表示，它的时间复杂度为O(|V|²)；若使用邻接表表示，其时间复杂度仍为O(|V|²)

如果边上带有负权值，Dijkstra算法不适用

2. 弗洛伊德各顶点最短路径

Floyd算法时间复杂度O(|V|³)

弗洛伊德允许图中带负权值的边，但不允许有包含负权值的边组成的回路。弗洛伊德算法同样也适用与带权无向边

关键路径

带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图为用边表示活动的网络，简称为AOE网。

在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；网中也仅存在一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。把关键路径上的活动称为关键活动。

对于关键路径，注意以下几点：

• 关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期
• 网中的关键路径并不唯一

拓扑排序

有向无环图：一个有向图中不存在环，则称为有向无环图，简称DAG图。

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足以下条件时，称为该图的一个拓扑排序。

• 每个顶点出现且只出现一次
• 若顶点A在序列中排在顶点B前面，则在图中不存从顶点B到顶点A的路径

或者定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中顶点B出现在顶点A后面。每个DAG图都是一个或多个拓扑排序序列。

DAG图进行拓扑排序的算法：

1. 从DAG图中选择一个没有前驱的顶点并输出
2. 从图中删除该顶点和所有以它为起点的有向边
3. 重复前两步知道DAG图为空或当前图中不存在无前驱的顶点为止

拓扑排序的时间复杂度为O(|V|+|E|)