数据结构基础学习之（图）

主要知识点

• 图的概述
• 图的存储结构
• 图的遍历
• 最小生成树
• 最短路径
• 拓扑排序
• 关键路径

一、图的概念

图的定义：

• 图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V,E）。

• 图中的数据元素称为顶点

基本概念

• 无向图：全部由无向边构成的图称为无向图(Undirected Graph).
• 有向图： 全部由有向边构成的图称为有向图(Directed Graph).

6.1无向图和有向图.png

• 权： 在图的边或弧中给出相关的数（非负），称为权。
• 网：图上的边或弧带权则称为网。

6.2无向网和有向网.png

• 无向完全图(Undirected Complete Graph)：无向图，边的取值范围是0到n(n-1)/2；边数达到最大值n(n-1)/2条边的无向图称为无向完全图

• 有向完全图(Directed Complete Graph): 有向图，边的取值范围是0到n(n-1)；边数达到最大值n(n-1)条弧的有向图称为有向完全图

• 稠密图和稀疏图： 在具有n个顶点，e条边的图G中， 如果含有的边较少（`）,则称图G为稀疏图，否则为稠密图

• 子图： 假设有两个图G=(V,{E}),和G' = (V',{E'}),如果V' 属于V,E'属于E,则称G' 为G的子图

6.3子示意图.png

• 邻接点： 假若顶点v 和顶点w 之间存在一条边（或弧）， 则称顶点v 和w 互为邻接点。
• 顶点的度（Degree）：是图中与该顶点相关联边的数目， 顶点V的度记为D(V)
• 入度和出度: 在有向图中，以顶点V为终点的弧称为入度,记为 ID(V);以顶点V为起点的弧称为出度，记为 OD(V)；该顶点V的度为D(V) = ID(V) + OD(V)
• 所有顶点度和与边数e的关系：`; 即所有顶点度的和为所有边数的两倍
• 路径（Path）：在一个图中，路径是从顶点u到顶点v所经过的顶点序列，即{u=v0,v1,...,vi=v}
• 路径长度： 路径上的边数或弧的数目
• 回路（环）： 第一个顶点和最后一个顶点相同的路径
• 初等路径： 序列中顶点不重复出现的路径
• 初等回路（环）：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
• 连通图（Connected Graph）： 在无向图中，从顶点u到到顶点v有路径，则称顶点u与顶点v连通，图中任意两个顶点连通，则称该图为连通图

连通图.png

• 连通分量(Connected Component)：无向图中的极大连通子图称为连通分量

• 强连通图：在有向图中， 图中任意两个顶点连通，则称该图为强连通图

强连通分量.png

• 强连通分量：有向图中的极大连通子图称为强连通分量
• 强连通图只有一个强连通分量，即其本身
• 生成树： 是极小的连通子图，它包含图中全部n个顶点，但只有足以构成一棵树的n-1条边
• 生成森林： 对于非连通图，每个连通分量可形成一棵生成树，这些生成树组成了该非连通图的生成森林。

二、图的存储结构

1. 邻接矩阵（Adjacency Matrix）：

• 邻接矩阵：用来表示顶点之间的相邻关系的矩阵

• 无向图的邻接矩阵是 对称阵，可以采用压缩存储

• 有向图的邻接矩阵一般不对称

• 使用邻接矩阵存储图，所需要的存储空间只与顶点数有关

• 顶点的度：

  • 在无向图邻接矩阵中，第i行或第i列的非零元素的个数正好是第i个顶点的度
  • 在有向图邻接矩阵中，第i行非零元素的个数正好是第i个顶点的出度，第i列非零元素的个数正好是第i个顶点的入度

• 示意图

有向图的邻接矩阵.png 无向图邻接矩阵.png

• 邻接矩阵 完整实现代码

2. 邻接表（Adjacency List）

1. 顶点的度:
   • 无向图中，顶点的度等于该顶点邻接表中边结点的个数, 如下图顶点v1的度为2
   • 有向图中，顶点的出度等于该顶点邻接表中边结点的个数；入度需要遍历整个邻接表或建立一个逆邻接表； 如下图的顶点v0, 由邻接表知出度为1，逆邻接表知入度为2

7-4-6无向图邻接表.png 7-4-7有向图的邻接表.png

• 对于n个顶点和e条边的无向图，其邻接表有n个顶点和2e个边结点
• 对于n个顶点和e条边的有向图，其邻接表有n个顶点和e个边结点
• 所以：对于稀疏图，使用邻接表比使用邻接矩阵更省空间

2. 邻接表 完整代码

3. 图的遍历

1. 类型：

• 深度优先遍历（Depth_First_Search，DFS）, 类似树的前序遍历
• DFS.java

DFS遍历的序列：01374256 .gif

• 广度优先遍历（Breadth_First_Search, BFS）， 类似树的层次遍历
• BFS.java
  BFS遍历的序列: 01234567 .gif

4. 最小生成树(Spanning Tree) 可视化

概念：

• 一个有n个顶点的连通图的生成树只能有n-1条边。
• 图的生成树不唯一，遍历方法不同生成树不同，遍历起点不同生成树不同
• 最小生成树： 在一个网的所有生成树中，权值综合最小的生成树称为最小生成树(Minimum Cost Spanning Tree)

构造最小生成树的准则：

1. 只能使用该图中的边构造最小生成树
2. 当且仅当使用n-1条边连接图中的n个顶点
3. 不能使用产生回路的边

克鲁斯卡尔算法(Kruskal)

1. 步骤：

• 假设图G = (V,E)是一个具有n个顶点的连通无向图，T = (V,TE)是网G的最小生成树， V是T的顶点集，TE是T的边集
• 一、 T的初始化状态为T = (V, NULL), 即开始时，最小生成树T是图G的生成零图
• 二、 将图G中的边按照权值从小到大的顺序依次选取，若选取的边未使生成树T形成回路，则加入TE中，否则舍弃，直到TE中包含n-1 条边为止

2. 示意图

   
   6.15Kruskal's Algorithm.png

3. Kruskal.java 邻接矩阵实现

普里姆算法（Prim）

1. 步骤：

• 假设图G = (V,E)是一个具有n个顶点的连通图，T = (U,TE)是网G的最小生成树， U是T的顶点集，TE是T的边集
• 一、从图G中找一个顶点，作为开始点， 放入顶点集U中；顶点集U用来保存构造最小生成树的顶点
• 二、从顶点集U中所有顶点的邻接点中，找出边(不能构成回路)上权最小的邻接点；把权值最小的边加入TE集合，相连的邻接顶点加入顶点集合U中
• 三、重复步骤二，直到顶点集合U == V，则TE必定有n-1条边，最小生成树T构造完毕

2. 示意图

   
   6.16Prim's Algorithm.png

3. Prim.java 邻接矩阵实现

5. 最短路径

1. 最短路径： 两个顶点之间经过的边上权值之和最少的路径； 路径上第一个顶点称为源点，最后一个顶点称为终点
2. 迪杰斯特拉(Dijkstra) 算法

• 基本思想：
  1. 通过Dijkstra计算图G中的最短路径时，需要指定开始计算的顶点s
  2. 此外，还需要引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
  3. 初始化时，把指定开始计算的顶点s加入集合S中；而集合U中是除s之外的顶点，并且U中顶点的路径是起点s到该顶点的路径。
  4. 然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。
  5. 重复步骤4； 直到遍历完所有顶点
• 图解 (图来自 skywang12345)
  Dijkstra's Algorithm.png
• 实现
  ShortestPath_Dijkstra.java

3. 弗洛依德(Floyd) 算法

• 基本思想

1. 通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。
2. 假设图G中顶点个数为N，则需要对矩阵S进行N次更新。
3. 初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。
4. 接下来开始，对矩阵S进行N次更新。
5. 第1次更新时，如果"a[i][j]的距离" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i与j之间经过第1个顶点的距离")，则更新a[i][j]为"a[i][0]+a[0][j]"。同理，第k次更新时，如果"a[i][j]的距离" > "a[i][k]+a[k][j]"，则更新a[i][j]为"a[i][k]+a[k][j]"。更新N次之后，操作完成！

• 图解

  
  ShortestPath_Floyd.png

• 参考 https://www.cnblogs.com/skywang12345/p/3711532.html

• ShortestPath_Floyd.java

6. 拓扑排序

• 概念：

1. 有向无环图: 无环的有向图称为有向无环图（Directed Acycline Grap,DAG）
2. 顶点活动网： 顶点表示活动，弧表示活动之间的优先制约关系，称为这种有向图为顶点活动网（Activity On Vertex,AOV）
3. 判读有向环：若AOV网 不能得到拓扑有序序列，则必定存在有向环

• 拓扑排序步骤：

1. 在AOV网中选择一个没有前驱的顶点输出
2. 从AOV网中删除该顶点以及从它出发的弧
3. 重复步骤1和2， 直到AOV网为空，，或者剩余子图中不存在没有前驱的顶点，后一种情况则说明该AOV网存在有向环。

• 图解(图来自)
  

  TopologicalSort.png

• 代码实现
  TopologicalSort.java

7. 关键路径

术语

1. AOE网：
   以顶点表示事件，弧代表活动，权表示活动需要的时间顶点表示以它为弧头的所有弧代表的活动已完成，所有以它为弧尾的弧代表的活动可以开始
2. 源点和汇点：
   正常情况(无环)下，网中只有一个入度为零的点,称为源点
   一个出度为零的点,称为汇点。
3. 关键路径：
   完成整个工程的最短时间是从源点到汇点的最长路径的长度(路径长度等于路径上各边的权之和)
   这条具有最大长度的路径称为关键路径
4. ee(i)：表示事件Vi的最早发生时间
5. le(i)：表示事件Vi的最迟发生时间；
6. e(k)：活动ak=<vi，vj>的最早开始时间
7. l(k)：活动ak=<vi，vj>的最迟开始时间;定义e(i)=l(i）的活动叫关键活动；
8. l(k)-e(k)：完成活动ak的时间余量

步骤

• 示意图（来源网上）

  
  criticalpath.png

1. 求ee(j): 从源点V1出发,令ee(V1)=0, 按照拓扑排序序列求其余各顶点的最早发生时间，ee(j) = max{ee(i)+ len<vi,vj>}; len<vi,vj>}是弧<vi,vj>上的权值；如：ee(V2) = ee(V1) + a1 = 0+6=6; ee(V5) = ee(v2) + a4 = 6+1=7
2. 求le(i): 从汇点出发，令 ，按照逆拓扑排序序列求其余顶点的最晚开始时间le(i); le(i) =min{ le(j)-len<vi,vj>}；len<vi,vj>}是弧<vi,vj>上的权值; 如：令le(V9)= ee(V9) = 18; le(V8) = le(V9) - a11 = 18-4 = 14;
3. 求每一项活动ai 的最早开始时间 e(i) = ee(j) 和最晚开始时间 l(i) = le(j) - len<vi,vj>;
   若e(i) == l(i) ,则为关键活动。如上图： e(a1) = ee(V1) = 0, l(a1) = le(V1) - 0= 0; e(a2) = ee(V1) = 0 , l(a2) = le(V3) - a2 = 6-4=2

代码实现

• CriticalPath.java