拓扑排序 示例：

对一个有向无环图(Directed Acyclic Graph，DAG)G进行拓扑排序，是将G中所有顶点排成线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前
一种可能的拓扑排序结果2->8->0->3->7->1->5->6->9->4->11->10->12

算法分析

拓扑排序的方法
从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它；
从网中删去该顶点，并且删去从该顶点发出的全部有向边；
重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。

Python代码如下：

解法1：用邻接矩阵表示图的拓扑排序

import numpy as np


def topological_sort(g):
    n = len(g)
    # 获取所有入度为0的结点
    q = []
    for j in range(n):
        flag = True
        for i in range(n):
            if g[i][j] == 1:
                flag = False
                break
        if flag:
            q.insert(0, j)

    li = []  # 记录结果
    while len(q) > 0:
        # p出队，把从p出度的数据置为0
        p = q.pop()
        li.append(p)
        for i in range(n):
            if g[p][i] == 1:
                g[p][i] = 0  # 去掉连通
                # 如果结点i的入度为0则入队结点i
                in_degree_count = 0
                for u in g:
                    if u[i] == 1:
                        in_degree_count += 1
                if in_degree_count == 0:
                    q.insert(0, i)

    return li


if __name__ == '__main__':
    # 用邻接矩阵表示图
    # 初始化图的数据，连通的标记为1
    g = np.zeros(shape=(13, 13), dtype='int')
    # g[i][j] = 1 表示 i -> j
    g[0][1] = g[0][5] = g[0][6] = 1
    g[2][0] = g[2][3] = 1
    g[3][5] = 1
    g[5][4] = 1
    g[6][4] = g[6][9] = 1
    g[7][6] = 1
    g[8][7] = 1
    g[9][10] = g[9][11] = g[9][12] = 1
    g[11][12] = 1

    result = topological_sort(g)
    print(result)

输出结果：[2, 8, 0, 3, 7, 1, 5, 6, 4, 9, 10, 11, 12]

解法2：用邻接表表示图的拓扑排序

def topological_sort2(g):
    n = len(g)
    # 计算所有结点的入度
    in_degree = [0] * n
    for i in range(n):
        for k in g[i]:
            in_degree[k] += 1
    # 入度为0的结点
    in_degree_0 = []
    for i in range(n):
        if in_degree[i] == 0:
            in_degree_0.insert(0, i)

    li = []  # 记录结果
    while len(in_degree_0) > 0:
        # p出队
        p = in_degree_0.pop()
        li.append(p)
        for k in g[p]:
            # 对应结点的入度减1
            in_degree[k] -= 1
            if in_degree[k] == 0:
                in_degree_0.insert(0, k)

    return li


if __name__ == '__main__':
    # 用邻接表表示图
    g2 = [[]] * 13
    g2[0] = [1, 5, 6]
    g2[2] = [3]
    g2[3] = [5]
    g2[5] = [4]
    g2[6] = [4, 9]
    g2[7] = [6]
    g2[8] = [7]
    g2[9] = [10, 11, 12]
    g2[11] = [12]
    result2 = topological_sort2(g2)
    print(result2)

输出结果：[0, 2, 8, 1, 3, 7, 5, 6, 4, 9, 10, 11, 12]