图
图的基本概念¶
- 简单路径就是顶点不重复出现的路径。（回路不算，但是有简单回路）
习题笔记¶
- 极大连通子图要求子图必须连通，而且包含尽可能多的顶点和边；极小连通子图既要保持子图连通，又要使得边数最小。
图的存储及基本操作¶
邻接矩阵法¶
邻接表法¶
十字链表、邻接多重表¶
图的基本操作¶
图的遍历¶
广度优先遍历（BFS）¶
深度优先遍历（DFS）¶
图的应用¶
最小生成树(最小代价树， Minimum-Spanning-Tree, MST)¶
- Prim（定点找权值最小的边）
- Kruskal（每次都选最小的边）
- 只能用于无向图！！！
贪心思想
最短路问题¶
BFS¶
Dijkstra¶
Floyd¶
有向无环图描述表达式¶
有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）
不唯一
拓扑排序¶
- 如何判断拓扑序列唯一？
- 每次让入度为0的点进入队列，再让它相邻的点入度 -= 1，再进行入队操作，若队列中含有多个入度为0的点，则不唯一；若整个过程中队列中元素个数一直 <= 1，那就唯一
关键路径¶
- v - vertex(点) e - early l - late
-
求解顺序
-
从源点用拓扑排序求点的最早开始时间（ve），ve[源点] == 0
-
从汇点用逆拓扑排序求点的最晚开始时间（vl），ve[汇点] == vl[汇点]
-
求活动的最早开始时间（e），每个活动的最早开始时间即为对应弧尾的最早开始时间
-
求活动的最晚开始时间（l），每个互动的最晚开始时间即为对应弧头的最晚开始时间减去弧的权值
-
最早开始时间和最晚开始时间相等的活动即为关键路径(可能不唯一)
活动的最晚开始时间与最早开始时间之差称为时间余额，就是可以拖延的时间
