图的存储结构

邻接矩阵

*item 存每个顶点的信息

**matrix 存二维的邻接矩阵

邻接表

  • 顶点跟上顶点后的子节点标记
  • 有tag用来存储顶点是否访问过

邻接多重表

  • 特指无向图的结构，因为其特性不用tag来标记
  • 增加边的话，直接加在边节点尾部，null后面

十字链表

  • 有向图的邻接多重表，因此有了出度、入度的概念

图的遍历

深度优先算法

广度优先算法

最小生成树

生成树：极小连通子图

最小生成树：对于带权连通图（网络），权值总和最小

克鲁斯卡尔算法

像并查集一样，森林变成树

普利姆算法

一个一个加进去

最短路径

迪杰斯特拉算法 正数

  1. 确定最短路径
  2. 用1的点迭代修改极短路径

贝尔曼-福特算法

  1. 迭代修改极短路径

弗洛伊德算法

  1. 二维的迭代修改极短路径

活动网络

AOV

  • 例子：先修课程

  • AOV网络中若没有有向环，则可以进行拓扑排序，且拓扑序列不唯一

  • 使用邻接表存储，因为只有出度没有入度，因此用InDegree数组存储入度信息

AOE

  • 例子：工程完成时间
  • 量
    • 最早发生时间
    • 最晚发生时间
    • 时间余量