首页
登录 | 注册

拓扑排序


layout: post
title: 最小生成树 Prim Kruskal
date: 2017-04-29
tag: 数据结构和算法
---

目录

  • TOC
    {:toc}

拓扑排序(AOV网络)

  • 排课的时候,根据课程的难易程度及知识体系有些课是要先上有些课需要后上,那么在给定了一些课的先后顺序,我们怎样来安排这些课的总体顺序呢?

  • 实际中拓扑排序的应用必入关键路径问题,一般用于安排项目的工序。

  • 首先明确下拓扑序的概念:如果图中从v到w有一条有向路径,则v一定排在w之前。满足此条件的顶点序列称为一个拓扑序。
    拓扑排序
  • AOV如果有合理的拓扑序,必定是有向无环图。

  • 具体我们怎么实现算法呢?简单的可以直接:

每次都选择入度为0的顶点,并把它和它的边一起从图中删除。
删除其事就是将与它相邻的顶点的入度减一。
算法的效率很大部分决定于找到入度为0的点,但是当图是稀疏图时,顺序扫描的方法就显得效率低下。那么有没有更好的办法呢?

拓扑排序

  • 一种很好的方法就是将入度为0的顶点放入一个容器中(栈或队列),然后没将相邻点入度减一的同时检查它的入度是否降为0,是的话就放入容器中。

拓扑排序

代码实现:

/* 邻接表存储 - 拓扑排序算法 */
 
bool TopSort( LGraph Graph, Vertex TopOrder[] )
{ /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
    int Indegree[MaxVertexNum], cnt;
    Vertex V;
    PtrToAdjVNode W;
       Queue Q = CreateQueue( Graph->Nv );
  
    /* 初始化Indegree[] */
    for (V=0; V<Graph->Nv; V++)
        Indegree[V] = 0;
         
    /* 遍历图,得到Indegree[] */
    for (V=0; V<Graph->Nv; V++)
        for (W=Graph->G[V].FirstEdge; W; W=W->Next)
            Indegree[W->AdjV]++; /* 对有向边<V, W->AdjV>累计终点的入度 */
             
    /* 将所有入度为0的顶点入列 */
    for (V=0; V<Graph->Nv; V++)
        if ( Indegree[V]==0 )
            AddQ(Q, V);
             
    /* 下面进入拓扑排序 */ 
    cnt = 0; 
    while( !IsEmpty(Q) ){
        V = DeleteQ(Q); /* 弹出一个入度为0的顶点 */
        TopOrder[cnt++] = V; /* 将之存为结果序列的下一个元素 */
        /* 对V的每个邻接点W->AdjV */
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
            if ( --Indegree[W->AdjV] == 0 )/* 若删除V使得W->AdjV入度为0 */
                AddQ(Q, W->AdjV); /* 则该顶点入列 */ 
    } /* while结束*/
     
    if ( cnt != Graph->Nv )
        return false; /* 说明图中有回路, 返回不成功标志 */ 
    else
        return true;
}

拓扑排序的应用--关键路径问题(AOE网络)

  • 用顶点表示活动,用弧表示活动间的优先关系的有向图:称为顶点表示活动的网(Activity On Vertex Network),简称为AOV网。

  • 与AOV网对应的是AOE(Activity On Edge)网即边表示活动的网。AOE网是一个带权的有向无环图。网中只有一个入度为零的点(称为源点)和一个出度为零的点(称为汇点)。其中,顶点表示事件(Event),弧表示活动,权表示活动持续的时间。

  • 通常,AOE网可用来估算工程的完成时间。

假如汽车生产工厂要制造一辆汽车,制造过程的大概事件和活动时间如上图AOE网:我们把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动叫关键活动。那么,显然对上图AOE网而言,所谓关键路径:开始-->发动机完成-->部件集中到位-->组装完成。路径长度为5.5。如果我们试图缩短整个工期,去改进轮子的生产效率,哪怕改动0.1也是无益的。只有缩短关键路径上的关键活动时间才可以减少整个工期的长度。例如如果制造发动机缩短为2.5天,整车组装缩短为1.5天,那么关键路径为4.5。工期也就整整缩短了一天时间。好吧! 那么研究这个关键路径意义何在?

假定上图AOE网中弧的权值单位为小时,而且我们已经知道黑深色的那一条为关键路径。假定现在上午一点,对于外壳完成事件而言,为了不影响工期:外壳完成活动最早也就是一点开始动工,最晚在两点必须要开始动工。最大权值3表示所有活动必须在三小时之后完成,而外壳完成只需要2个小时。所以,这个中间的空闲时间有一个小时,为了不影响整个工期,它必须最迟两点动工。那么才可以保证3点时与发动机完成活动同时竣工,为后续的活动做好准备。

拓扑排序

  • 对AOE网有待研究的问题是:

    • (1)完成整个工程至少需要多少时间?

    • (2)那些活动是影响工程进度的关键?

拓扑排序

Reference


相关文章

  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • Entityframework Core in action Entityframework Core in action是 Jon P smith 所著的关于Entityframework Core 书籍.原版地址. 是除了官方文档外另一 ...
  • MongoDB【快速入门】
    1.MongDB 简介 MongoDB(来自于英文单词"Humongous",中文含义为"庞大")是可以应用于各种规模的企业.各个行业以及各类应用程序的开源数据库.作为一个适用于敏捷开发的数据库,Mo ...
  • 实验4
    Part1: #include <stdio.h> const int N=5; int main() { int a[N] = {1, 2, 3, 4, 5}; int i; for(i=0; i<N; i++) pri ...
  • 实验四实验报告
    实验结论 Part 1 数组将类型相同的一组数据在内存中连续存放,由实验可看出数组中元素的内存地址是连续的,不同类型数据计算机为其分配的内存空间是不同的. Part 2 定义一维数组a,须指明它包含的元素个数和元素类型,通过数组名和下标的形 ...
  • 对于初学者,或者没有接触过网络编程的程序员,会觉得网络编程涉及的知识很高深,很难,其实这是一种误解,当你的语法熟悉以后,其实基本的网络编程现在已经被实现的异常简单了. 网络通信作为互联网的技术支持,已被广泛应用在软件开发中,无论是Web,服 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.076 s.
京ICP备10005923号