拓扑排序的代码实现是怎样的？

本文共计1613个文字，预计阅读时间需要7分钟。

归并排序，是一种针对有向无环图的算法，主要用于解决前后继关系，同时可用来判断有向图中是否存在环态结构、栈、有向图：我们这节课要讲的是包括有向图在内的算法，所以先来把‘有向图’的定义解释一下。

拓扑排序，是一个针对有向无环图的算法，主要是为了解决前驱后继的关系，同时可以用来判断有向图是否存在环状结构 铺垫

有向图：我们这节要讲的算法涉及到有向图，所以我先把有向图的一些概念说一下，文章后面就不做解释啦。首先有向图节点与节点之间是用带箭头的线连接起来的。节点有出度和入度的概念，连线尾部指向的节点出度加1，连线头部，也就是箭头指向的节点入度加1。看下面这个例子，A的入度为0，出度为2，B的入度为1，出度为1，C的入度为1，出度为1，D的入度为2，出度为0。

邻接表：邻接表是存储图结构的一种有效方式，如下图所示，左边节点数组存储图中所有节点，右侧邻接表存储节点的相邻节点。

简介

这篇文章我们要讲的是拓扑排序，这是一个针对有向无环图的算法，主要是为了解决前驱后继的关系，即我们在完成当前事项的时候需要先完成什么事项，其实这在我们流程控制里面用的挺多的。看下面这个图，我们需要先完成A事项，然后才能去完成B，C事项，B，C事项的属于并列的，没有先后顺序，但是对于D事项需要在B，C事项完成之后才能进行。而拓扑排序能够帮助我们找到这个完成事项的合理顺序，同时我们看上面这个例子，A事项完成之后，B，C事项是没有先后顺序的，不管是先完成B还是C都符合条件，所以拓扑排序的顺序序列不是完全一定的。

工作过程

首先拓扑排序对应操作的是一个有向无环图。无环图，则肯定存在至少一个结点入度为0。在当前情况下，我们需要查找入度为0的节点进行操作，入度为0，表示当前节点没有前驱节点，或者前驱节点已经处理，可以直接操作。