`
endual
  • 浏览: 3560990 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

有向无环图 拓扑排序

 
阅读更多

package endual.tuopupaixu;

/**
 * 拓扑排序
 * 
 * 拓扑排序的思想虽然不寻常,但是还是很简单的
 * 有两个步骤要去考虑
 * 步骤1 
 *   找到一个没有后续的顶点(这是从有向图的角度是做了,而不能用最简单的那种图去考虑问题了)
 *      顶点的后续也是一些顶点,他们是该节点的直接“下游”  也就是说这些节点与他们由一条边相连,并且
 *      边的方向指向它们。如果有一条边从A指向B,那么B是A的后续
 *      
 *  步骤2
 *    从图中删除这个顶点,在列表的前面插入顶点的标记
 *    
 *  重复步骤1和步骤2,直到所有的顶点都从图中删除。这时,列表显示的顶点顺序就是拓扑排序的结构了
 * @author Endual
 *
 *   说明:
 *   删除顶点似乎是一个极端的步骤,但是它是算法的核心,如果第一个顶点不处理,算法就不能计算出要处理的是第二个顶点。
 *   如果需要,也可以在其他地方存储图的数据(顶点列表或者邻接矩阵),然后再排序完成后恢复他们就可以了
 *   
 *      算法能够执行是因为,如果一个顶点没有后续,那么它肯定是拓扑序列的最后一个了。一旦删除它,剩下的顶点中比如有一个
 *      没有后续的,所以它成为下一个拓扑序列的最后的一个了。依次类推。
 *   
 *   
 *   拓扑排序算法可以既可以是连通图,也可以用于非联通图。这可以模拟另外一种两个互不相关的目标的情况。
 *   例如同时获得数学学位和急救资格的证书。
 */

/**
 * 环和树
 * 
 * 环是拓扑排序无法处理的。
 * 图的话=====》》》》 不是环就是树了
 * @author Endual
 *
 *要计算是不是要环也是简单的:
 *   如果N个顶点的图有超过N-1条边,那么就肯定有环的存在了。可以尝试下画一个没有环而有N个顶点的,N条边的图,这样就可以lij
 *   理解了
 *   
 *   拓扑排序必须在无环的有向图中进行的(有向无环图)
 *
 *
 */
public class GrapnSort {

}
 
分享到:
评论

相关推荐

    有向无环图拓扑排序并输出圈

    在"有向无环图拓扑排序并输出圈"的问题中,我们首先需要检查图是否为DAG。这通常通过DFS实现,使用一个颜色数组记录每个节点的状态(白色表示未访问,灰色表示正在访问,黑色表示已访问)。如果在DFS过程中发现一条...

    有向无环图的全拓扑排序

    求出有向无环图的所有拓扑排序序列的C语言程序实现

    图的拓扑排序和有向无环图的判断

    图的拓扑排序和有向无环图(Directed Acyclic Graph, DAG)的判断是图论中的基础概念,广泛应用于计算机科学的多个领域,如任务调度、编译器设计等。拓扑排序是对有向无环图进行线性排列的一种方式,而DAG的环检测则...

    有向图的拓扑排序判断是否存在环

    在本场景中,我们讨论如何判断一个有向图是否存在环,并在无环的情况下进行拓扑排序。 首先,我们需要理解有向图的基本概念。有向图是由顶点(节点)和有方向的边组成的。边的方向决定了从一个顶点到另一个顶点的...

    有向图若有环,输出环,否则,拓扑排序

    对于有向图,若发现它是有环的,那么输出它的环,否则,就输出它的拓扑排序

    利用拓扑排序算法判别有向环

    标题"利用拓扑排序算法判别有向环"指出,我们可以通过执行拓扑排序来检测有向图中是否存在环。这是因为如果在有向图中存在环,那么尝试进行拓扑排序时会出现矛盾,无法为所有节点找到一个无环的线性顺序。具体来说,...

    有向图的拓扑排序报告

    有向图的拓扑排序是图论中的一个重要概念,它主要应用于有向无环图(DAG,Directed Acyclic Graph)。在数据结构的学习中,拓扑排序是对有向图节点的一种线性排序,使得对于图中的每一条有向边 `(u, v)`,节点 `u` ...

    深度优先搜索与有向无环图的拓扑排序(java实现)

    深度优先搜索(Depth First Search, DFS)是一种在图或树数据结构中遍历或搜索的算法。...此外,为了确保拓扑排序的正确性,需要确保图确实是一个DAG,即无环的有向图。在执行拓扑排序之前,可以先检查是否存在环。

    带有环判断的拓扑排序来自西安工业大学课程设计

    拓扑排序(Topological Sort)是一种线性排序算法,它只适用于有向无环图(DAG)。这种排序方式能够将图中的顶点排成一个线性的序列,使得对于任意一对顶点u和v,如果图中存在从u到v的路径,则u在序列中出现在v之前...

    拓扑排序算法

    拓扑排序是图论中的一个重要概念,特别是在有向无环图(DAG,Directed Acyclic Graph)处理中显得尤为关键。这种算法的目标是为图中的节点找到一个线性顺序,使得对于每一条从节点u到节点v的有向边,u都在v之前出现...

    简单拓扑排序——源码

    拓扑排序是图论中的一个重要概念,主要应用于有向无环图(DAG,Directed Acyclic Graph)。在这样的图中,节点之间的关系是有方向性的,而拓扑排序就是找到一个线性的顺序,使得对于每一条边 (u, v),节点 u 都在这...

    C# 图 拓扑排序

    拓扑排序是对有向无环图(DAG,Directed Acyclic Graph)的一种排序方法,它将图中的节点排成一个线性的序列,使得对于每一条从节点u到节点v的有向边(u, v),u都在v之前出现。在C#中实现拓扑排序,我们需要理解几个...

    c语言实现图的拓扑排序

    拓扑排序是对有向无环图(DAG,Directed Acyclic Graph)的一种线性排序,它使得对于图中的每一条有向边 (u, v),节点 u 的排序位置总是在节点 v 之前。在实际应用中,例如课程安排、项目依赖关系解决等场景,拓扑...

    数据结构拓扑排序课程设计.docx

    如果无法进行下去,意味着图中存在环,而拓扑排序在有环的有向图上是无法执行的。 为了实现拓扑排序,通常会使用到【邻接表】这种数据结构来表示图。邻接表是一种节省空间的图表示方法,它由一个顶点数组和一组链表...

    操作系统 拓扑排序算法

    任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为...或者直到图中没有无前趋的顶点为止,此情形表明有向图中存在环。

    VC++拓扑排序算法

    拓扑排序是图论中的一个重要概念,特别是在有向无环图(DAG,Directed Acyclic Graph)处理中非常实用。VC++是一种强大的编程语言,它提供了丰富的库支持来进行各种算法的实现,包括拓扑排序。在本教程中,我们将...

    拓扑排序 整体 拓扑排序

    拓扑排序是图论中的一个重要概念,主要应用于有向无环图(DAG,Directed Acyclic Graph)。在计算机科学中,特别是在数据结构和算法领域,拓扑排序常常用于解决依赖关系的排序问题,例如课程安排、任务调度等场景。...

    拓扑排序的完整应用课设报告

    拓扑排序是图论中的一个重要概念,特别是在有向无环图(DAG)处理中非常有用。它是对有向无环图的顶点的一种线性排序,使得对于每一条有向边 (u, v),顶点 u 都在这个排序中出现在顶点 v 之前。拓扑排序的特性使得它在...

    数据结构课设拓扑排序源代码(教学计划安排)

    拓扑排序是一种基于有向无环图(DAG)的排序算法,可以应用于教学计划的安排。根据课程之间的依赖关系,拓扑排序可以生成一个符合逻辑的教学计划。 拓扑排序算法的思想是首先将所有入度为零的顶点入队列,然后输出...

    图 拓扑排序 深度搜索 广度搜索 最小生成树

    最后,**最小生成树(MST)** 是一个无向图中边的子集,它包含了图中的所有节点,并且任何两个节点之间都有路径相连,同时这个子集的总权重是最小的。求解MST是图论中的经典问题,常见算法包括Prim的贪心算法和...

Global site tag (gtag.js) - Google Analytics