数据结构－图－拓扑排序

github地址：https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E5%9B%BE_%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F.md

图_拓扑排序

一个不存在回路的AOV网，可以将其应用在各种各样工程项目的流程图中。例如：让你实现一个画流程图的软件，那你在内存中怎么组织流程图呢？？

也就是保证工程项目能够顺利进行

AOV网

在一个表示工程的有向图中，定点表示活动，弧表示活动之间的优先关系

拓扑排序

其实就是对一个有向图（包含AOV）构造拓扑序列的过程

算法原理

数据结构中in表示该定点的入度，因为是AOV网，因此从入度为0的点开始

  1. 找到所有入度为0的顶点（p点），入栈
  2. 读栈，从图中删除p点，然后把与p相连的弧尾顶点in值减1，判断这些顶点有无入度（in的值）为0者，有则入栈
  3. 读栈取出一个新的顶点，急需执行步骤2，直到全部顶点操作完毕

例如：下面的图第一次就是找到三个顶点入度为0，全部入栈

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 【数据结构和算法】笔记
    课程介绍 先修课：概率统计，程序设计实习，集合论与图论 后续课：算法分析与设计，编译原理，操作系统，数据库概论，人...
    ShellyWhen阅读 2,382评论 0赞 3
  • 图结构
    https://zh.visualgo.net/graphds 浅谈图形结构https://zh.visualgo...
    狼之独步阅读 4,259评论 0赞 0
  • 《大话数据结构》总结
    第一章 绪论 什么是数据结构？ 数据结构的定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,844评论 0赞 19
  • 数据结构与算法（六），图
    图是一种比线性表和树更复杂的数据结构，在图中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。图是一种多对...
    Alent阅读 2,364评论 1赞 22
  • java成品源码 - 草稿 - 草稿
    ¥开启¥ 【雷霆战机】 〖http://pan.baidu.com/s/1kVstszX〗 《解压源码后直接用AI...
    小菜c阅读 3,815评论 0赞 5