图

图的基础

定义：图G由顶点集V和边集E组成，记为 G = (V, E) ，其中 V(G) 表示图G中顶点的有限非空集； E(G) 表示图G种边的集合。若V={ $v_1, v_2,...$ }则|V|表示G中顶点的个数，E={(u, w)|u∈V,v∈V}，则|E|代表G中边的条数。

由上面的定义可知：图是不可以为空的，因为图的顶点集合是非空的。但边集可以为空，若边集为空则图中全是点，而没有点之间的关系。

图的术语

有向图

E为有向边（又称弧）的有限集合，则图G为有向图。有向边是顶点的有序对，记为<v, w>，其中v，w是顶点，v是弧尾，w是弧首，读作从v到w的弧，又称v邻接到w。

有向图在互相连接的节点之间只能以特定的方向移动。使用带单向箭头的线来表示有向边。

无向图

E为无向边的有限集合，则图G为无向图。无向边是顶点的无序对，记为(v, w)或(w, v)。v和w互为邻接点。边(v, w)依附于w和v，或称(v, w)和v，w相关联。

无向图可以在互相连接的节点之间可以以任意方向移动。

简单图、多重图

图G满足：不存在重复的边；不存在顶点到自身的边，则称该图为简单图。多重图就是违背了上面的要求。

顶点的度、入度和出度

这个要分有向图和无向图进行分析：

无向图：讨论的是度，就是一个顶点上与多少顶点相连，其度就为多少。
有向图：讨论的是入度和出度，入度是多少弧的弧首指向该顶点，出度是多少弧的弧尾在该顶点上。

除此之外，还要补充的是 无向图的全部顶点的度之和等于边数的二倍，因为一条边与两个顶点关联，多一条边就会多两个度。

有向图全部顶点的入度之和与出度之和相等，并且分别等于边数。

路径、路径长度和回路

对于不带权的图而言，顶点 $v_p 到 v_q$ 之间的一条路径是指的顶点序列，如： $v_p, v_{i1}, v_{i2}, ..., v_q$ ，路径中的相关联的边也可以作为路径的构成要素。

其中路径上经历的边的数量为路径长度。

对于带权的图而言，路径长度为路径 $v_p, v_{i1}, v_{i2}, ..., v_q$ 上所有边上的权值之和。

若路径中的第一个顶点和最后一个顶点相同，则为一个回路或环。若一个图有n个顶点，且其边的数量大于n-1，则必定有环。

简单路径、简单回路

重点是不重复。在路径序列中，顶点不重复出现的路径称为简单路径。除第一个和最后一个顶点外，其余顶点不重复出现的回路为简单回路。

距离

顶点p到顶点q，若存在最短路径，则此路径的长度称为p到q的距离，否则记两定点距离为∞

子图

$有两个图G=(V, E)和G^{'}=(V^{'}, E^{'})，若V^{'}是V的子集，且E^{'}是E的子集，则称G^{'}为G的子图。$

$假设满足V(G^{'}) = V(G)则称G^{'}为G的生成子图。$

注意

形成子图首先是两者都要为图，所有并非V和E的任何子集都能构成G的子图。如果取得E的子集中边含有的顶点在取得V的子集中没有，这样的话，图都构不成何谈子图呢！

连通、连通图和连通分量

这里的讨论是针对无向图的。假设无向图中的两个顶点v，w之间存在路径，则称v和w之间是连通的。若无向图中的任意两个顶点之间都是连通的，则称该图G为连通图，否则称为非连通图。

在无向图中的极大连通子图称为连通分量。

强连通图、强连通分量

这里的讨论是针对有向图的。和上面的无向图类似，假设有向图中的两个顶点v，w之间相互都存在路径，则称两个顶点是强连通的。若有向图中的任意一对顶点都是强连通的，则称该图为强连通图。

有向图中的极大强连通子图称为该有向图的强连通分量。

tips

这里任意两个顶点之间路径并不是说每两个顶点之间存在相互的弧，而是说只要能到达就算，所以一个图是强连通图时，其最少的边为n条，沿一个方向形成一个圈时使用的边最少。

生成树、生成森林

连通图的生成树是包含图中所有顶点的一个极小连通子图（图连通但是要边数最小）。也就是说若一个图的顶点有n个，那该图的边就有n-1条。

对于一个生成树而言，若添加一条边就会形成回路，若减少一条边就会变得不再连通。

生成森林和生成树类似，就是图为非连通图，经历多次上面生成树的过程就生成了由多棵树组成的森林。

显然可以看见生成树不止一种，只要满足上述的条件无论怎样生成都是合理的。

边的权、网和带权路径长度

图的边上带有存在特殊意义的数值时，这个数值就称为该边的权值。边上带权的图就称为网。一条路径上所有边的权值之和称为该路径的带权路径长度（路径长度）。

完全图

无论是有向图还是无向图，其完全图都是边最多的情况。也就是任意两个顶点之间都存在边（弧）。

对于无向图，因为(v, w)和(w, v)是一致的，故其完全图（无向完全图）的边有 $\frac {n(n - 1)}{2}$ 条。

对于有向图，因为<v, w>和<w, v>是不同的，故其完全图（有向完全图）的弧有 $n(n - 1)$ 条。

稠密图、稀疏图

对于图而言的稠密和稀疏是针对边数和顶点个数的关系。

一般而言，若图的 $|E| < |V|log_2{|V|}$ ，则称该图为稀疏图（就是边数相对于顶点数太少了）。

有向树

有一个入度为0的顶点并且其余顶点的入度均为1的有向图，该图被认为是一颗有向树。

图的存储和基本操作

图的存储需要详细保存顶点集和边集。我们需要掌握一下四种表示方法。

邻接矩阵法

采用一个一维数组对图的顶点信息进行维护，一个二维数组对图的边信息进行维护。该二维数组称为邻接矩阵。

若图G=(V, E)中有n个顶点，则邻接矩阵A为n x n的，将G中的顶点编号为 $v_1, v_2, ..., V_n$ ，则有：

A[i][j] = \begin{cases} 1, & \text{若 } (v_i, v_j) \text{ 或 } \langle v_i, v_j \rangle \text{ 是 } E(G) \text{ 中的边} \\ 0, & \text{若 } (v_i, v_j) \text{ 或 } \langle v_i, v_j \rangle \text{ 不是 } E(G) \text{ 中的边} \end{cases}

而对于带权图而言，对应的 $A[i][j]$ 位置上存放具体的权值。而没有边（弧）的 $A[i][j]$ 存放0或者∞则可。

使用C语言表示的结构体为：

小贴士

无向图的邻接矩阵是对称矩阵，故在存储时可以采用压缩存储。
邻接矩阵表示法的空间复杂度为O( $|V|^2$ )。
如果是简单的应用则可以直接省略顶点信息，只使用邻接矩阵。

图的邻接矩阵表示法的特点：

无向图的邻接矩阵为对称矩阵，故存储时只需使用 $\frac {n(n + 1)}{2}$ 个元素的顺序表。
无向图的邻接矩阵中，第i行（列）非零元素的个数为顶点i的度 TD( $v_i$ )。
有向图的邻接矩阵中，第i行的非零元素个数为顶点i的出度OD( $v_i$ )，第i列的非零元素个数为顶点i的入度ID( $v_i$ )。
邻接矩阵表示法可以很容易得出两个顶点之间是否存在边（弧），但是如果需要知道到底有多少条边就需要一次遍历每行每列了。
稠密图是适用于邻接矩阵法表示。

邻接表法

十字链表

邻接多重

基本操作

图的应用

最小生成树

对于一个带权连通无向图，生成树不同，其树的权（树中的所有边的权值之和）也会有所不同。而其中权最小的树就为最小生成树（MST）。

有两种不同的算法：

1. Prim算法

开始时从图中任取一个顶点，加入到树T中，此时T中就只有一个顶点，然后选择T中顶点上权值最小的边（所有T中所有没有使用过的边），得到该边和与之对应的顶点并将该顶点和对应的边加入T中，依次类推，直到所有的顶点全部加入。

这样得到的生成树T就为最小生成树。

其时间复杂度为O( $|V|^2$ )，是与边无关的，所以适用于求边稠密的图的最小生成树。

2. Kruskal算法

按照边上权值递增的方式进行构造最小生成树。

开始时将图视为有n个无边的顶点G = {V, {}}，从所有边集中选出最小且未使用的边，若将边加上后不会形成环则加入边，否则选择下一条边。

其时间复杂度为O( $|E|log_2|E|$ )，是与点无关的，所以适用于求点稠密的图的最小生成树。

注意

对于Prim和Kruskal算法，都只适用于求带权连通无向图的生成子树。

因为在带权有向图中没有带权有向图的概念。

最短路径

在之前学的广度优先搜索查找最短路径是对于无权图的。在这里可以是带权图，把从一个顶点 $v_0$ 到图中的其他任意一个顶点 $v_i$ 的一条路径所经过边上的权值之和定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

其实之前的无向图可以视为每条边权值为1的带权完全图。经历一次广度优先搜索就可以知道每个顶点到开始搜索的顶点的最短路径了，就像是从开始搜索的顶点向外的波。

而对于带权图的最短路径问题可以分为两类：

求图中某一顶点到其余顶点的最短路径，使用Dijkstra算法。
求图中任意两顶点之间的最短路径，使用Floyd算法。

Dijkstra算法

大名鼎鼎的GPS就是使用的这个算法来寻找当前位置到目标位置的最短路径，是贪心算法的典型应用。

总的来说，Dijkstra算法的原理为：

该算法会从源节点开始，寻找其他节点与该节点之间的最短路径。
该算法会记录其他节点到源节点的最短路径长度，并在寻找到更短路径长度时更新。
一旦找到了源节点到其他节点 $A_i$ 之间的最短路径，则将 $A_i$ 标记为已访问并添加到路径中。
重复上述过程直到所有节点都已访问。

Dijkstra算法实现：

设置一个集合S记录已求得最短路径的顶点，初始化时将源点 $v_0$ 放入S中。

Dijkstra算法要实现需要几个辅助数组：

final[] (标记各顶点是否已经找到最短路径， $v_i$ 找到了则令final[i]为true并将其加入S)
dist[] (记录从源点 $v_0$ 到其他顶点当前的最短路径长度，初始规则为：若从 $v_0$ 到 $v_i$ 有边（弧），则dist[i]为对应的权值，否则置为∞)
path[] (path[i]表示从源点到顶点i之间i的最短路径的前驱节点，可以根据path[i]一步一步的找到前一个节点从而得到完整的最短路径)

步骤（通俗易懂版，在上面的三个数组中最为重要的就是 dist[] 所以我们在这不讨论其余两个数组）：

带权有向图G采用邻接矩阵 $arcs[i][j]$ 表示。

初始化S、dist[]，将源点 $v_0$ 加入到S中， $dist[i] = arcs[0][i]$ 。

Dijkstra算法只能用于权值为正的图中，若图中存在权值为负的边则该算法就不起作用了，并且不论图采用何种方式存储其时间复杂度都为O( $|V|^2$ )。

Floyd算法

Dijkstra算法是求的源点到其余顶点之间的最短路径，格局小了，Floyd算法直接搂每队顶点之间的最短路径。

Floyd算法是允许边（弧）上的权值带有负值的，但是不能有回路，其时间复杂度为O( $|V|^3$ )。其实也是可以使用Dijkstra算法求每队顶点之间的最短路径问题，只需要对每个顶点都使用一次Dijkstra算法就可，其时间复杂度为O( $|V|^2|V|$ )，和Floyd算法一致。

有向无环图描述表达式

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

拓扑排序

AOV网： 若用有向无环图表示一个工程，其顶点表示活动，用有向边 $<v_i, v_j>$ 表示活动 $v_i$ 必须先于活动 $v_j$ 进行的关系，则将这种有向图称为顶点表示活动的网络，简称AOV网。

拓扑排序： 是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中B出现在A的后面。

拓扑排序就是对AOV网活动的顺序的一种排序，通俗的讲就是按活动可能发生的顺序排序，所以一个AOV网可能存在多个拓扑排序（活动发生的顺序不一定有具体的先后关系）。

更为详细的拓扑排序算法步骤：

从AOV网中选择一个入度为0的顶点并输出。
从AOV网中删除所有与以选择的顶点为起点的有向边。
重复1、2步骤直到AOV网中为空或不存在入度为0的情况（没有入度为0的话，该图一定存在环，就不属于DAG了）。

拓扑排序算法的C语言表示：

因为拓扑排序在删除顶点后还会删除以该顶点为起点的边（相当于要遍历一次图），所以图采用不同的存储结构会有不同的时间复杂度。

若采用邻接矩阵表示法则时间复杂度为O( $|V|^2$ )。

若采用邻接表表示法则时间复杂度为O(|V| + |E|)。

关键路径

AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的消耗（时间），称之为用边表示活动的网络，简称AOE网。

对于AOE网和AOV网，两者都是DAG图，但是前者边上有权值，后者没有，并且图中组成元素表示的含义也不同。

AOE网具有的性质：

只有在某顶点表示的事件发生后，从该顶点出发的各有向边代表的活动才能开始。
只有在进入某顶点的所有有向边代表的活动都结束时，该顶点代表的事件才能发生。
AOE网仅有一个入度为0的顶点，称其为源点（开始顶点），表示工程的开始；仅有一个出度为0的顶点，称其为汇点（结束顶点），表示工程的结束。

关键路径、关键活动：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，在关键路径上的活动称为关键活动。

注意

在带权图中的最大、最小路径长度是由所有路径中边上的权值之和大小决定的。路径MAX中边上的权值之和最大，则称MAX为具有最大路径长度的路径，反之亦然。

在这里认为AOE图中边上的权值指的是活动需要消耗的时间，则整个工程完成所需最短时间是关键路径的长度，也就是说工程完成所需的最短时间由关键路径上的活动消耗时间决定。

所以我们要掌握的重点就是怎样找到关键活动（边）。只要关键活动找到了，关键路径和最短完成时间就都有了。

注意

如果只是用人眼看，一下就可以找到关键路径，我们要掌握的是算法思想。

为了找出关键活动，引入5个要使用的参量：