本文来给大家讲解一下算法与数据结构图论中的拓扑排序，看完后相信你对拓扑排序的理解会更进一步。

入度与出度

入度与出度是针对有向图而言的，无向图并无入度与出度这一概念，对于有向图中的某个节点：

入度=指向该节点的有向边条数

出度=从该节点出发指向其他节点的有向边条数

        比如，在这个有向图中，根据入度与出度的计算规则我们可以得到每个节点的入度与出度，具体如下表所示：

各节点入度与出度

节点	入度	出度
A	0	1
B	1	2
C	1	2
D	1	2
E	2	1
F	1	1
G	3	0

拓扑排序的概念 

        拓扑排序是指对有向无环图（DAG）中顶点按依赖关系进行的线性排序，保证若存在边 u→v，则u 必在v之前出现。

        以下边这个图为例，由于节点选择的不同，对其进行拓扑排序可以得到ABCDEFG，ABCDFEG，ABCFEDG，ABCFDEG，ABDCFEG，ABDCEFG共计6种不同的结果。

拓扑排序方法

拓扑排序的方法非常简单，如下：

• 从DAG图中选择一个没有前驱（入度为0）的顶点并输出
• 从图中删除该顶点和所有以它为起点的有向边

重复上述两个步骤直到DAG图为空

注意，当排序过程中有多个入度为0的顶点时，可以任意选择，故拓扑排序的结果不唯一。

例题

例子是最好的学习工具，我们用一道例题来彻底弄清楚拓扑排序。

        首先，我们在图中找到入度为0的节点，显然只有顶点A符合，将其从图中去掉后加入到排序序列中，图变成了:

拓扑排序序列：A

        接着，在上一轮的图中继续寻找入度为0的节点，发现只有顶点B符合，将其从图中去掉加入到拓扑排序的序列中，图变成了:

拓扑排序序列：AB

        接着，在上一轮的图中寻找入度为0的节点，发现顶点C与顶点D同时符合条件，CD两个顶点中任意选择一个将其从图中去掉并加入到拓扑排序的序列中，图变成了:

拓扑排序序列：ABC

          接着，在上一轮的图中寻找入度为0的节点，发现顶点D与顶点F同时符合条件，DF两个顶点中任意选择一个将其从图中去掉并加入到拓扑排序的序列中，图变成了:

拓扑排序序列：ABCD

            接着，在上一轮的图中寻找入度为0的节点，发现顶点E与顶点F同时符合条件，EF两个顶点中任意选择一个将其从图中去掉并加入到拓扑排序的序列中，图变成了:

拓扑排序序列：ABCDE

         接着，在上一轮的图中寻找入度为0的节点，发现只有顶点F符合条件，将其从图中去掉并加入到拓扑排序的序列中，图变成了:

拓扑排序序列：ABCDEF

        最后，只剩一个顶点G入度为0，将其从图中去掉并加入到拓扑排序序列中，有向图为空，算法结束。得到了最终的拓扑排序序列：ABCDEFG。

        注意，在排序过程中我们多次遇到了同时存在多个入度为0节点的情况，这些节点的不同选择都会导致最终的拓扑排序序列不同。

        只有当每个点的入度和出度最多为1，即每次都只有一个入度为0的节点可供选择那么拓扑排序序列才唯一。

拓扑排序常见考点

• 1.若有向图的拓扑排序序列唯一，则图中每个点的入度和出度最多为1(因为要保证每次都只有一个入度为0的节点可供选择)。
• 2.“拓扑序列唯一” ≠ “原图唯一”。
• 3.用领接矩阵存储具有有序拓扑序列的有向图，则其领接矩阵必是三角矩阵，若不是三角矩阵则图中可能存在环。
• 4.在拓扑排序序列中，若顶点在之前，则有可能是:
• G中有一条到的弧
• G中没有弧但是有一条到的路径，比如：

总结

        以上便是拓扑排序的所有内容，如果对你有用，还请一键三连支持一下！😀