6.4 有向无环图

6.4-1 DAG描述表达式


数据结构

数据结构

6.4-2 拓扑排序


数据结构

  • AOV网（Activity On Vertex Network）：顶点表示活动，弧表示活动之间的优先关系
  • 实现：

    数据结构
  • 时间复杂度：
    • 邻接表：O(|V|+|E|)
    • 邻接矩阵：O(|V|2)
  • 逆拓扑排序

    数据结构

    数据结构

    数据结构

6.4-3 关键路径


数据结构

  • AOE网（Activity On Edge Network）：弧表示活动，顶点表示事件
    • 只有某顶点代表的时间发生后，该顶点出发的弧上的活动才能开始
    • 只有在进入某顶点的所有弧上的活动都完成后，该顶点代表的事件才能发生
  • 关键路径：从源点到汇点的最长路径
  • 关键活动：关键路径上的活动
  • 事件Vk的最早发生时间ve(k)：决定了所有从Vk出发的活动的最早开始时间
  • 活动ai的最早开始时间e(i)：决定了该活动弧的起点所表示的事件的最早发生时间
  • 事件Vk的最迟发生时间vl(k)：在不推迟整个工程完成时间的前提下，该事件必须发生的最迟时间
  • 活动ai的最迟开始时间l(i)：该活动弧的终点所表示的事件的最迟发生时间与该活动所需的时间之差
  • 求关键路径
    • 1）正大

      数据结构
    • 2）反小

      数据结构
    • 3）=起点

      数据结构
    • 4）=终点-

      数据结构
    • 5）相减

      数据结构
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家