图知识点总结_avo网络

思维导图链接：
链接：https://www.zhixi.com/view/3cc2bdf8
密码：5402

第6章

图

问题的提出

如何确保某城市的各个小区都能用上天然气，怎么样部署才能最省钱

对于工程项目的管理中，一个大的工程往往被分解成若干个子任务，子任务要何时开工，何时完工，哪些能同时开工？怎么样确保在整个工程中按时完成？

图的定义和基本术语

顶点是多对多的逻辑结构关系

结点：图中顶点

结点间关系：图中顶点之间的连线

无向图：边不带方向

有向图：边带方向

v入度

v出度

v的度

路径

路径长度

简单路径

简单回路

子图

方向和权

有向图

无向图

有向网

无向网

边和顶点数

无向完全图

有向完全图

稀疏图

稠密图

连通性

无向图

有向图

生成树和生成深林

图的结构描述

图抽象数据类型

数据对象：顶点集

数据关系：边集

基本操作

创建图

销毁图

依据值找顶点的存储地址

对某个顶点赋值

寻找某个顶点的第一个邻接关系的顶点

添加新的顶点

删除顶点和相关的边

添加边

删除边

深度优先遍历

广度优先遍历

图的存储结构

图的邻接矩阵表示

图的领接表表示

有向图的十字链表表示

无向图的多重链表表示

图的遍历

深度优先遍历（DFS）

递归遍历

栈实现非递归遍历

广度优先遍历（BFS）

递归遍历

队列实现非递归遍历

非连通图的深度（广度）优先遍历

图遍历算法的应用

求一条包含无向图中所有顶点的简单路径

起点的选择

顶点的邻接点次序

要有保存路径上顶点的数组

寻找失败的时候，要能回退

判断有向图中是否存在环

判断弧<v,w>，顶点v的深度优先遍历是否比w的深度优先遍历先结束

先结束则说明存在环，否则不存在

求无向图的顶点a到顶点i的简单路径

在连通图中，对a进行深度优先遍历，必能找到顶点i

没到达目标顶点，则回退，删除保存的顶点

求无向图的顶点vi到vj最短的路径

对vi进行广度优先遍历

修改队列的操作

找到的时候，通过队尾指针可以找到这个路径

图的连通性

无向图的连通分量和生成树

求最小生成树

普利姆算法

最小生成树的不断成长的过程

每一次选取顶点，并依据较小值更新该顶点到它顶点的距离

在更新后的距离中，找到最短距离的边进行选择顶点（不选择无穷大，也不选择已经被选择过的）

存储结构

定义最大值MAXCONST

定义最小代价数组

定义顶点标记访问数组

克鲁斯卡尔算法

子树不断合并的过程

将边按小到大排序

每一次按小到大选取边

判断边两边的顶点所属的子树根编号，根编号不相同则选取该边，相同则跳过改变

最短路径（带权有向图）

求某个源点到其余个点的最短路径算法

迪杰斯特拉算法

算法过程

选取出发点

比较出发点到各点之间的距离，选取最小值的边

将边和顶点存储起来

在比较通过选取的顶点到各顶点之间的距和原来的距离进行比较，更据较小值进行更新

再次重新选取顶点和最小的边（不选取已经选取和标记过的顶点和边）

重复上述操作，当最小值边为MAXCONST的时候，算法结束

存储结构

邻接矩阵表示有向网

标记顶点数组

路径存储

求图中每一对顶点之间的最短路径算法

弗洛伊德算法

算法过程

对于任意两点，判断加入图中的一个点的时候，通过该店到路径是否比原来的距离小，如果小的就更新两点之间的最短距离

对图中的每一个点都选择一次

最后更新的距离数组就是两点之间的最短距离

迭代的过程

存储结构

距离数组d

两点之间的关系数组path

就是在两个点之间添加一个而外点，可能会使两个顶点之间的距离变小

有向无环图及其应用

应用

有向无环图是描述有公共子式的表达式的有效工具

有向无环图是描述一项工程或系统进行过程控制的有效工具

AVO网络以及拓扑算法

顶点表示活动，弧表示活动之间的优先关系

拓扑序列：有优先关系的顶点，先的顶点在后的顶点之间前；没有关系位置任意，计算机将编号小的顶点放在前面

拓扑算法：用栈来实现，先将入度为0的顶点依次入栈；然后出栈，将和栈顶元素的顶点有邻接关系的顶点入度－1；往复操作，当栈为空的时候，循环结束。拓扑序列和顶点数相同，则有拓扑序列；否则没有（存在环）

AOE网络及关键路径

顶点表示事件的发生，弧表示活动，权值表示时间

事件的最早发生时间

事件的最迟发生时间

活动最早开始时间

活动最迟开始时间

关键路径：最长路径

关键活动：最长路径上的活动