今天收获

• 拓扑排序：就是先找到入度为0的点，然后将它取出来，同时把相关的边去掉

• 逆拓扑排序：就是出度为0的点开始，方法同理

• 最短通路：
• 先画出n行n列的表，将点标上去，（行顶点，列步骤——个人习惯 但考试 行步骤 列 点）
• 然后在步骤第1步那块除起点外全部都是 +∞，后面同理（只要还没到达的点都是 +∞）
• 从起点开始看相连的有哪些边，将权值标上去
• 接着选权值最小的那条边，到达新的点
• 接着更新相连的边的权值，如果已经走过了的点（不管），如果新的权值比原来已经存在的小，则更新，当已经是最小（一般就是到达这个点后）了，就做个标记，表示最小了
• 重复上述步骤
• 最短路径就是每一步走的那个点
• 缓冲时间也叫剩余通量

• 事件最早/晚发生时间
• 最早发生时间（从左到右加起来和最大的路径）：
• 先在每个点上标 （Vx ，Vy）然后看每个点实际的发生时间，找出大的值，写上去
• 原点和终点的最早和最晚是一样的
• 最晚发生时间从右往左找减完最小的

• 活动最早/最晚开始时间：
• 先从起点开始，每次看该点指向的边，下标从小到大写
• 最早：抄上面的时间，重点是前边顶点 Vx（Vx，Vy） 的最早发生时间
• 最晚：每次用对应点 Vy 的最晚发生时间 减去 y 点 到 x点的的权值
• 时间余量：最晚 - 最早

• 关键活动是时间余量为0的点

• 关键路径：就是时间余量为0组成的路径

• 边数=节点数-1 + 无回路or连通才能构成树

• 完全图的边数 = [n*（n-1）]/2，n为顶点数

• 无向图中，所有顶点的度数之和 = 边数的两倍 （正方形）

• 无向图G有生成树 当且仅当 G是连通图

• 求最小生成树的权总和
• 给权排序
• 描点，将边数置0
• 选边（权最小，且不构成回路）
• 一直重复第三步，直到 边数=顶点数-1

• 前缀码判断：不能包含出现过的两位以上连续的前缀码 如 aaab 前面有aa了

• 树是边数最多的无向图，树是边数最少的连通图

• th9.1： 在有向图中 奇顶点有偶数个

• th9.4：正方形—— 通路边数<= n-1 回路<=n

待复习内容

日记内容

• 下午因为爬楼claude和接单的事情耽搁的比较久，所以浪费了些时间

• 不知道为啥最近某处不太舒服，我怀疑是洗冷水洗的，得停两天冷水了

任务完成情况

计划