拓扑排序

在大学里面。我们要学习非常多种类的课程。当中有一些课程必须以还有一种课程为基础。我们怎么样安排课程才干保证学每一门课的时候它的前驱课程都上过?

                      

要保证课程不会发生冲突(每一门课都必须安排在它的前驱课程之后)。就要找出最前面的课程,安排这些课程先上。

        


       假设我们用结点表示课程任务,箭头表示先后关系。那么我们能够得一个有向图。我们怎么才干将这些课程排成一个序列呢?这个序列要保证箭头左边的点不会出如今箭头右边点的前面。

           解决的办法事实上非常easy
1、在有向图中选一个没有前驱的顶点且输出之。


2、从图中删除全部以它为尾的弧。


3、反复上述两步,直到所有顶点已经输出,或者是当前图中不存在无前驱的顶点为止。

后一种情况则说明图中有环存在。

       

    详细样例看链接:hdoj 1285,代码加解释!

 

   有矩阵,邻接表,队列,三种写法!

原文地址:https://www.cnblogs.com/mfmdaoyou/p/7209888.html