拓扑排序，拓扑排序是什么

本文目录一览

1，拓扑排序是什么
2，数据结构拓扑排序
3，请解释下拓扑排序的定义和实现方法别复制百度百科
4，什么叫拓扑排序

1，拓扑排序是什么

拓扑排序就是，把一个偏序排成全序，这个东西在离散数学上边讲

拓扑排序是什么

2，数据结构拓扑排序

拓扑排序说白了就是依次遍历没有前驱节点的节点。分析：这6个节点中，最早是0没有前驱，所以先遍历0；去掉0节点和他的指针向量后，发现1和5都没有前驱，这个时候看你的程序怎么写了，不过就此题来说，你可以随便取一个，1也行，5也行，我先取1吧；去掉1和他的指针向量，发现2和5都没前驱，同上，我选2；照上面一次做下去，最后得到： 0-1-2-3-5-4 当然：0-1-5-2-3-4 0-1-2-5-3-4 0-5-1-2-3-4 也都对。

数据结构拓扑排序

3，请解释下拓扑排序的定义和实现方法别复制百度百科

拓扑排序所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下：给出有向图G=（V，E），若结点的线形序列V1,V2,...Vn满足条件：对于i,j(1≤j<i≤n)，Vi和Vj之间没有边。求线形序列V1,V2,...Vn的过程就称为拓扑排序，这个线形序列就称为拓扑序列。【拓扑排序主要思想】有向图可以拓扑排序的条件是：图中没有环。具体方法： ⑴ 从图中选择一个入度为0的点加入拓扑序列。 ⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。反复执行这两个步骤，直到所有结点都已经进入拓扑序列。【实例：士兵排队问题】有n个士兵(1≤n≤26)，依次编号为A,B,C,...，队列训练时，指挥官要把一些士兵从高到矮排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果，记作（p1>p2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD，FABD，ABFD 【输入】 k行，每行a b，表示a>b 【输出】一个可行的排队方案【输入样例】 A B B D F D　　【输出样例】 ABFD

请解释下拓扑排序的定义和实现方法别复制百度百科

4，什么叫拓扑排序

就系一种结构咯

拓扑排序(Topological Sort) 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。注意： ①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 ②若图中存在有向环，则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。 ⑤当有向图中存在有向环时，拓扑序列不存在【例】下面(a)图中的有向环重排后如(b)所示，有向边和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。无前趋的顶点优先的拓扑排序方法该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为： NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有人度为0的顶点)do{ 从G中选择一个人度为0的顶点v且输出之；从G中删去v及其所有出边； } if(输出的顶点数目<|V(G)|) //若此条件不成立，则表示所有顶点均已输出，排序成功。 Error("G中存在有向环，排序失败！")； } 对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0，C1，C2，C4，C3，C5，C7，C9，C6。注意：无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。