队列Queue--拓扑排序

对一个有向无环图(Directed Acyclic Graph, DAG)G进行拓扑排序，将G中所有顶点排成线性序列，使得图中任意一对顶点u、v，若边(u,v)∈E(G)，则在线性序列中u出现在v之前。

队列Queue--拓扑排序示例

拓扑排序的方法：

1. 在有向图G中任选一个没有前驱(即入度为0)的顶点并输出它；

2. 从G中删除该顶点，并且删除去从该顶点出发的全部有向边；

3. 重复上述两步，直到剩余的网络中不再存在有前驱的顶点为止。

有向无环图 demo

Python Demo:

# !/usr/bin/env python
# -- coding: utf-8 --
# @Time : 2017/7/10 11:46
# @Author : Albert·Sun
# @Version : 0.10α
# @Description: (1).用数组grap存放图G的连接关系，grap[i][j]：顶点j指向顶点i,即边E(j->i),此处边权简化为1; (2).Pyhton中的List结构模拟Queue

def topo(graph):
    indegree = []
    for i in range(len(graph)):
        if sum(graph[i]) is 0:
            indegree.append(i)

    while len(indegree) > 0:
        cur = indegree.pop(0)
        print cur+1,
        for i in range(len(graph)):
            graph[i][cur] = 0
        graph[cur][cur] = -1
        # print graph

        for i in range(len(graph)):
            if graph[i][i] is not -1 and graph[i].count(1) is 0:
                if indegree.count(i) <= 0:
                    indegree.append(i)
        # print indegree

if __name__ == "__main__":
    grap = [[0, 0, 0, 0, 0, 1],
            [1, 0, 0, 0, 0, 1],
            [1, 1, 0, 0, 0, 1],
            [1, 0, 1, 0, 0, 0],
            [1, 1, 0, 1, 0, 0],
            [0, 0, 0, 0, 0, 0],
            ]
    topo(grap)

输出：6 -> 1 -> 2 -> 3 -> 4 -> 5

注：

拓扑排序的本质是不断地输出入度为0的点；

该算法可用于判断图中是否存在环。