算法9拓扑排序.ppt_第1页
算法9拓扑排序.ppt_第2页
算法9拓扑排序.ppt_第3页
算法9拓扑排序.ppt_第4页
算法9拓扑排序.ppt_第5页
已阅读5页，还剩42页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、1、拓扑排序、1、概念1、directed acyclic graph非循环图形直接图2、Activity On Vertices(AOV)网络牙齿直接图形称为以顶点表示活动的网络。如果图中有边，则VI是VJ的直接前兆。Vj不允许在VI的直系AOV网络中循环。也就是说，活动不能以自己为前提，4、计划、施工流程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般把工程分成几个叫“活动”的子项目。完成牙齿活动后，牙齿工程就可以完成了。例如，电脑主修学生的学习是项目，各课程的学习是整个工程的一部分活动。这些课程中，有些需要先修课程，其他课程不需要。这样，有些科目有主导关系，有些科目可以并行学习

2、。5，6，1，AOV中的拓扑顺序序列：按线性顺序排列每个顶点(表示每个活动)，以满足AOV网络中必须存在的所有灯泡和后续关系。“拓扑对齐”是根据AOV网络中顶点彼此的优先级关系将它们排成线性序列的过程。检测AOV网络中的循环方法：对于在直接图中构成顶点的拓扑顺序序列，如果网络中的所有顶点都在拓扑顺序序列中，则该AOV网络不应有循环。第二，拓扑排序，第7，拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-c11-C6-由于图中存在回路B、C、D、9，因此为aa有n个顶点。1直接在AOV网络中选择并输出没有灯泡的顶点。2删除图中的牙齿顶点，删除它发送的所有方向边。3重复上述步骤1、2，直

3、到所有顶点都输出，拓扑按顺序形成，拓扑对齐完成。或者图中有未输出的顶点，因此无法再找到没有灯泡的顶点。此时，AOV网络必须有定向环。a、b、c、g、h、d、f、e、a、b、h、c、d、g、f/顶点域struct node * next/链域JD；标头节点：typedef struct tnode int ind/入射域struct node * link/链域TD；TD gM，AOV网络的存储方式-相邻表指示13，1牙齿相邻表中所有输入度为零的顶点在堆栈2堆栈不为空时输出堆栈顶部元素Vj并撤回堆栈。在相邻的表中找到Vj的直系Vk，将Vk的粒度减少1。如果Vk的立场为0，则在堆栈3中重复以上操作，直到堆栈为空。堆栈为空时，如果输出的顶点数不是N牙齿，则方向图中有一个环。否则，拓扑将被排序。，4，拓扑排序算法实现，14，15，输出序列：6，16，17，输出序列：6，18，输出序列：6，19，输出序列：6，20，输出序列3，27，输出序列：6 1，4，3，3输出序列：6 1 3 2 4 5，44；输出序列：6 1 3 2 4，5，45；输出序列：6 1 3 2 4 5，5，46，5；拓扑排序算法status topological sort (aa /每个顶点口也InitStack(查找S/堆栈为空的for

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论