数据结构之图

图是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图中的顶点的集合，E是图G中边的集合。

• 线性表中的数据元素叫元素，树中的数据元素叫结点，图中的数据元素叫顶点。
• 线性表中可以没有元素，叫空表，树中可以没有结点，叫空树，而图中不能没有顶点，在定义中，V是顶点的集合，有穷且非空。
• 线性表中，相邻的数据元素具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

关于图的各种定义：
无向边&无向图
若顶点Vi到顶点Vj之间的边没有方向，则称这条边为无向边，用无序偶对（Vi，Vj）来表示。如果任意两个顶点之间的边都是无向边，则称该图为无向图。无向图表示法：G=（V1，{E1}），其中V1={A,B,C,D}，E1={（A,B），（B,C），（C,D），（A,C）} (无向边小括号)

有向边&有向图
若顶点Vi到顶点Vj的边有方向，称该边为有向边，也叫作弧。使用有序偶<Vi,Vj>表示，Vi为弧尾，Vj为弧头。如果任意两个顶点之间的边为有向边，则称该图为有向图。有向图的表示法：G=（V2，{E2}），其中V2={A,B,C,D}，E2={<A,D>,<B,C>,<C,A>,<B,A>} ( 有向边尖括号)

相关术语
在图中，如果不存在顶点到自身的边，且同一条边不重复再出现，则称该图为 简单图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。n的顶点的无向完全图的边的数目：n*(n-1)/2

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。n个顶点的有向完全图的弧的数目：n*(n-1)

有些图的边或弧具有与他相关的数字，这种与图的边或弧相关的数叫做权，带权的图通常称为 网。

图G=（V，{E}），图G'=(V'，{E'})，且 V属于V’，E属于E'，称G为G'的子图。

无向图中，顶点v的度为与该顶点相关联的边的数目，即为TD（v）。图中边的数目为各顶点的度的和的一半。

有向图中，顶点v的度为入度和出度之和，入度为以顶点V为头的弧，记作ID（v），出度为以顶点V为尾的弧，记作OD（v）。有向图中的边的数目为顶点的ID（v）,或者OD（v）。

图中顶点V到顶点V'之间的路径为顶点的序列，对于无向图该序列中相邻的点之间的边属于无向图的边的集合，对于有向图该序列中的相邻点组成的具有方向性，属于有向图的弧的集合。路径的长度为弧或边的数目。

连通图相关术语
在无向图中，如果顶点V到顶点V'有路径，称为V和V'是连通的。如果对于图中任意两个顶点都是连通的，则称该图为连通图。

无向图中的极大连通子图称为连通分量，连通分量强调：

• 要是子图
• 子图要是连通的
• 连通子图含有极大顶点数
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边

而有向图中，如果对于每一对属于顶点集的Vi，Vj，从Vi到Vj和从Vj到Vi都存在路径，则称该有向图为强连通图，有向图中的极大强连通子图称作有向图的强连通分量。

连通图的生成树
一个连通图的生成树是一个极小的连通子图，含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。

如果一个有向图恰有一个顶点的入度为0，其他顶点的入度均为1，则是一棵有向树。一个有向图由若干有向树构成森林。

图的抽象数据类型

image

图存储结构

• 邻接矩阵
  图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（为邻接矩阵）存储图中的边或弧的信息
  无向图：
  

  image
  有向图：
  image
  无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一 定是对称阵
  网中存储权值：
  image
  image

• 邻接表
  对于边数相对于顶点较少的图，使用邻接矩阵会对存储空间造成一定的浪费。这时可以采用将数组与链表相结合的存储方式，称为邻接表。
  顶点数组中存储顶点信息和一个指向第一个邻接点的指针，边表结点由存储某顶点的下标和边表中下一个结点的指针域构成
  无向图邻接表
  

  image
  有向图邻接表
  image
  有向图有方向，边表中可以按照以该顶点的弧尾储存，或者弧头存储
  带权值的网图：
  image
  边表再添加权值域存储权值

• 十字链表
  对于有向图来说，邻接链表是有缺陷的。关心出度问题，想了解入度情况，需要遍历整个图。将邻接链表和逆邻接链表结合。
  顶点数组的数据元素除了数据域和出度指针域外，添加入度指针域，即指向弧头为该顶点的弧边结点
  弧边结点为两个数据域两个指针域，数据域分别记录该弧的弧头和弧尾的顶点下标，指针域一个指向顶点出度的弧，一个指向顶点入度的弧
  

  image
  十字链表将邻接表和逆邻接表结合，可以方便找出某一个顶点的入度和出度的弧，因此在有向图中，十字链表是非常好的数据结构。

• 邻接多重表
  对于无向图的邻接表，若关注的重点是顶点，那么邻接表可以满足要求，若是更关注边的操作，如对已访问的边做标记，删除一条边等，那么使用邻接表就会相对比较麻烦，要找到这条边对应的两个节点进行处理。使用邻接多重表结构：
  | ivex | ilink | jvex | jlink |
  ivex和jvex是与某条边依附的两个顶点在顶点表中的下标，ilink是顶点ivex所指的下一条边，jlink是顶点jvex所指的下一条边，在构造图的边结点时采用头插法，这样每个边结点会被两个指针所指：
  

  image

• 边集数组
  边集数组有两个一维数组构成。一个存储顶点信息，一个存储边的信息，边数组的每个数据元素由每条边的起点下标和终点下标以及权重组成。边集数组关注的是边的集合，边集数组中查找顶点的度需要扫描整个边数组，效率不高，更适合对边依次处理的操作，不适合对顶点的相关操作。
  

  image

图的遍历
从图中某一顶点出发访遍图中其与顶点，且使每一个顶点仅被访问一次，该过程叫做图的遍历

深度优先遍历DFS
也称为深度优先搜索，简称DFS。从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这里是对于连通图，若是非连通图，则对其连通分量扥别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
深度优先其实就是一个递归过程，类似一棵树的前根序遍历过程。

广度优先遍历BFS
广度优先搜索类似于树的层序遍历，将与该顶点的邻接的顶点通过入队和出队，完成层序搜索。

深度优先适合有明确的目标，以找到目标为主要目的的情况，而广度优先适合在不断扩大搜索范围以找到相对最优解的情况。

最小生成树
一个连通图的生成树是一个极小的连通子图，包含图中所有的顶点，只有足以构成一棵树的n-1条边。构造连通网的最小代价生成树称为最小生成树。找出最小生成树的常用算法：

image
Prim算法
Prim算法从某一顶点开始

• 遍历该顶点与其他顶点的之间的边的权值，并存入权值数组
• 并找出其中权值最小的边的对应顶点，记录下该顶点下标
• 同时将最小权值的边的两个顶点做标记，避免重复检索
• 将记录的顶点与其他顶点的权值与之前的权值数组比较
• 更新权值数组，记录下两者中较小的权值，如果有更新将记录的顶点的下标存入对应位置的下标数组

这样一轮检测完时，权值数组中储存的权值表示与当前权值最小的边的顶点有邻接关系的顶点对应的边的权值，下标数组中存储的是与当前权值最小的边的其中一个顶点邻接的未检索的其他顶点。对其他顶点重复进行上述操作，时间复杂度为0(n^2)，针对上图的Prim算法结果：

image

Kruskal算法
Kruskal算法从边开始，依次选择权值最小的边来构成最小生成树，比较重要的两步：

• 将边按照权值进行排序，从权值最小的边开始
• 检查被选择的边是否构成环路，如没有构成环路，则记录边的顶点下标，否则放弃这条边

因此，针对上图首先按照权值对边进行排序，得到：

image
使用Kruskal算法结果：
image
该算法与边有关，与判断环路相关的函数时间复杂度为loge ，对e条边的总体时间复杂度为O(eloge)

对比两个算法，Kruskal算法针对边展开，对于稀疏图Kruskal的效率会相对较高，而对于稠密图，即边比较多的情况下，Prim算法效率相对较高。

最短路径问题
对于非网图，由于没有权值，最短路径即为两顶点之间经过的边数最少的路径。
对于网图，由于带有权值，最短路径即为两顶点之间经过的边的权值之和最小的路径。
Dijkstra算法
Dijkstra算法是从网图的源点出发，依次计算到每个顶点的最短路径，直到最后目标点，并记录路径的前驱下标。
始终由当前的已知最短路径向与之相连的权值最小的路径扩散，此前与某一顶点直接相连的权值已经被记录在权值和的数组中，
若在扩散过程中发现间接路径的权值和小于直接路径的权值和，则之前的直接路径就会被间接路径覆盖掉，并更新前驱数组
这样就可以找出源点到其他每一个顶点的最小权值和路径。
对于以下的网图：

image
使用Djikstra算法得到的结果：
image
final数组用来确定从源点到哪些点的最短路径已经确定
D数组用来存储源点到对应的点的最短路径的权值和
P数组用来存储到对应路径的上一个点的下标
该算法的时间复杂度为O（n^{2），如果想要找出所有点对其他点的最短路径，则需要在外层再循环图中顶点个数次，时间复杂度为O（n}3）
Floyd算法
Floyd算法是通过找出每一个点与下一个点之间的最短距离，并记录下标，最后得到完整的路径。
而判断每一个点与下一个点的最短距离是通过比较起始点到结束点是直接路径短还是通过中间点的路径短，如果中间距离短就更新起始点到结束点的记录的路径值。由于需要遍历计算中间点，以及起始点和结束点，因此需要3层循环来确定每一个点到另一个点的最短路径，时间复杂度为O（n^3）
对于以下网图：
image
使用Floyd算法得到的结果：
image
image
image

AOV网
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先级关系，这样的有向图为顶点表示活动的网，称之为AOV（Activity On VertexNetwork）网。AOV网中的弧表示活动之间存在某种制约关系。AOV网中不能存在回路。
设G=（V，E）是一个具有n个顶点的有向图，V中的顶点序列V1,V2,……Vn,满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则称之为这样的顶点序列为一个拓扑序列。

拓扑排序
拓扑排序是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在回路的AOV网；如果输出顶点少了，即便是少了一个，也说明这个网存在回路，不是AOV网。

拓扑排序算法
对AOV网进行拓扑排序的基本思想是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为弧尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。
对以下有向无环图：

image
构建邻接表：
image
采用拓扑排序得到的结果：
image
最开始将入度为0的顶点入栈，即顶点0,1,3，然后依次出栈，同时删除该点与邻接点的连接关系，即将对应邻接点的入度减一，若果发现出现新的入度为0的点，再次加入到栈顶，直到最终栈中不存在入度为0的点。 拓扑排序整个算法，需要遍历顶点n次得到初次的入度为0的点，然后执行入度减一的次数为边数e
因此整个算法的时间复杂度为O（n+e）

关键路径
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称之为AOE（Activity On Edge）网。AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。对于一个工程一般都有一个开始和结束，因此正常情况下AOE网有一个源点有一个汇点。
AOE网路径上的各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径。
关键路径的算法：
找到AOE图中的每个活动的最早开始时间和最晚开始时间，然后比较他们，如果相等就说明这个活动在路径中没有空闲时间，则为关键活动，活动之间的路径就为关键路径
对于以下无环有向图，先使用拓扑序列算法求得各顶点的最早开始时间，再根据拓扑序列的反向顺序逆向求各顶点的最晚开始时间

image
使用关键路径算法得到的结果：
image
如果某一个工程存在多个关键路径，只提高某一条关键路径上的关键活动效率并不能提高整个工程的工期，必须同时提高在几条关键路径上的活动效率。