拓扑排序

实现代码

a, b, c, d, e, f, g, h = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h')
G = {
    a: [b, f],
    b: [c, d, f],
    c: [d],
    d: [e, f],
    e: [f],
    f: []
}
def res_topsort(G, S=None):
    # S是当前规模各个点的集合
    if S is None: S = set(G)
    if len(S) == 1: return list(S)
    # 随意出一点
    v = S.pop()
    seq = res_topsort(G, S)
    min_i = 0
    # 找出以v点为出边的是哪一元素，将其插入该元素后，如无，插入开头
    # 规模从小到大，每一次return 的 seq都是一个DAG
    for i, u in enumerate(seq):
        if v in G[u]: min_i = i + 1
    seq.insert(min_i, v)
    return seq
def topsort(G):
    count = dict((u, 0) for u in G)
    for u in G:
        for v in G[u]:
            count[v] += 1
    Q = [u for u in G if count[u] == 0]
    S = []
    while Q:
        u = Q.pop()
        # 将没有入边的节点插入
        S.append(u)
        # 每出一条边 减少 该没有入边的节点指向的节点 的入边
        for v in G[u]:
            count[v] -= 1
            if count[v] == 0:
                Q.append(v)
    return S
print res_topsort(G)
# ['a', 'b', 'c', 'd', 'e', 'f']

复杂度

求各顶点入度的时间复杂度是O(e)，即边的个数。
建零入度顶点栈的时间复杂度是O(n)，即顶点的个数。
每个顶点都需要进一次栈，出一次栈，然后把入度减一。执行的总次数也是边的个数。
所以时间复杂度是O(n+e)。