图解数据结构之图、邻阶矩阵、邻接表、拓扑排序、AOE网及其关键路径

图（Graph）

参考视频

1、概念

（1）图的定义

• 图是由两个集合组成V、E，记为G=(V,E)。
  • V是顶点（数据元素）的有穷非空集合
  • E是顶点偶对的有穷集合，这些点偶对称为边
• 无向图：每条边都是没有方向的图，没有箭头
• 有向图：如上，反之。每条边都是有方向的图
  • 顶点个数=表头结点个数
  • 边数=2倍表结点数

（2）基本术语

• 子图：

• 简单图： 如上图G1、G2都是

  • 不存在重复边
  • 不存在顶点的自身的边

• 多重图：

  • 若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图。多重图的定义和简单图是相对的

• 完全图（也称简单完全图）
  

• 稀疏图和稠密图

  • 边或弧的个数e < n logn的图为稀疏图，否则稠密图。（n为图的数量）

• 权和网

  • 图中的边可标上具有某种含义的数值，该数值称为边上的权
  • AOV网是有向完全图

• 有权图与无权图

  如果图中的边有各自的权重，得到的图是有权图。比如地铁路线图，连接两站的边的权重可以是距离，也可以是价格，或者其他。反之，如果图的边没有权重，或者权重都一样（即没有区分），称为无权图。

• 连通图

  如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。无向图中的一个极大连通子图称为其的一个连通分量。

• 图的存储

  常用的存储方式有两种**：邻接矩阵和邻接表。**

（3）知识图解

(4)图的遍历

遍历结果通常不唯一

• 深度优先：一条路走到黑，这条路不通了可以折返找没走过的路
• 广度优先：一行一行的遍历、或者一列一列的遍历，地毯式搜索

2、邻阶矩阵

• 无向图
  • 特点：
    1.无向图的邻接矩阵是对称的，且主对角线元素全为0(因为自己到自己没有边)。
    2.顶点i的度=第i行(列)中1的个数。
    3.完全图的邻接矩阵中，主对角元素为0，其余全为1，如果带权重的话没有连接写无穷。按0101这样写就行

• 有向图

  特点：
  有向图的邻接矩阵可能不是对称的。
  顶点的出度=第i行元素之和；
  顶点的入度=第i列元素之和；
  顶点的度=第i行元素之和+第i列元素之和。

3、邻接表

• 无向图

  • 邻接表不唯一
  • 有连接的都要指向

  

• 有向图

4、拓扑排序

• 入度：有箭头指向自己的为入度点

• 出度：有指向别人的箭头

  • 如4：入度为2，出度为2
  • 如1：入度为0，出度为2

• 拓扑排序：

  找没有入度的点输出，并去除所对应边，如图，因为1没有入度输出1，第二个图2没有入度输出2。如果有多个没有入度的随意选择

• 逆拓扑排序

  • 与拓扑排序相反，逆拓扑排序找没有出度的点
  • 如上图逆拓扑排序输出结果为：5、3、4、2、1

5、AOE网、关键路径

• AOE网

  AOE网（Activity On Edge Network）用边表示活动，用顶点表示事件（活动的完成）。边是带权的，表示活动需要的时间。

• 源点与汇点

  源点：入度为0的点，表示一个工程的开始。

  汇点：出度为0的点，表示一个工程的结束。

• 关键活动与关键路径

  在AOE网中，从源点到汇点最长的路径称为关键路径，在关键路径上的活动称为关键活动。

  因为AOE网中的活动是可以并行进行的，所以整个工程的时间开销，其实是最长路径的时间开销。即关键路径制约整个工程的工期。

• 关键路径应用

  • 计算

    事件最早发生时间 = 拓扑排序第一个点到各点权重和（多路径选最大值）

    时间最迟发生时间 = 逆拓扑排序的第一个点 - 到各点权重值（多路径选做差完最小的值）

    活动最早发生时间 = 弧尾的事件最早发生时间

    活动最迟发生时间 = 弧头事件最迟发生时间 - 权重（即该边权重）

    时间余量 = 活动最迟发生时间 - 活动最早发生时间