乐趣区

关于数据结构和算法:图论-拓扑排序

介绍

咱们把做从筹备食材,做菜到摆盘当作一个我的项目工程

当咱们每次只能做一个流动,并且咱们想要得出实现整个我的项目工程的程序

并且这个程序要确保咱们能实现整个工程

难道还有一个程序是咱们没法实现这个工程的?不是从左到右顺次做就行了吗?

还真有,例如

筹备食材,切番茄,打鸡蛋,炒鸡蛋,下番茄,混合翻炒,放调料,紫菜蛋花汤,摆盘

也能够依照这样的形式进行

筹备食材,紫菜蛋花汤,切番茄,下番茄,打鸡蛋,炒鸡蛋,混合翻炒,放调料,摆盘

又或者这样的形式进行

筹备食材,切番茄,下番茄,打鸡蛋,紫菜蛋花汤,炒鸡蛋,混合翻炒,放调料,摆盘

然而不能以这样的形式去进行

筹备食材,切番茄,下番茄,混合翻炒,打鸡蛋,下鸡蛋,放调料,紫菜蛋花汤,摆盘

因为都还没有鸡蛋,哪来的混合翻炒

到这里,咱们就能看出拓扑排序的作用了

就是 保障咱们的我的项目工程可能实现,具备实际意义

外围就一点:在每个流动开始时,保障它的所有前驱流动都已实现

例如,混合翻炒这个流动的所有前驱流动就是

筹备食材,切番茄,下番茄,打鸡蛋,炒鸡蛋

但紫菜蛋花汤并不属于混合翻炒的前驱流动,而是属于摆盘的前驱流动

实现

定义

退出移动版