【Python排序搜索基本算法】之拓扑排序

旧城等待， 2022-05-15 14:45 237阅读 0赞

拓扑排序是对有向无环图的一种排序，满足如下两个条件：

1.每个顶点出现且只出现一次；

2.若A在序列中排在B的前面，则在图中不存在从B到A的路径。

如上的无环有向图，v表示顶点：v=\['a','b','c','d','e'\]，e表示有向边：e=\[('a','b'),('a','d'),('b','c'),('d','c'),('d','e'),('e','c')\]，代码如下：

def indegree0(v,e):   
    if v==\[\]:  
        return None  
    tmp=v\[:\]  
    for i in e:  
        if i\[1\] in tmp:  
            tmp.remove(i\[1\])  
    if tmp==\[\]:  
        return -1  
   
    for t in tmp:  
        for i in range(len(e)):  
            if t in e\[i\]:  
                e\[i\]='toDel' \#占位，之后删掉  
    if e:  
        eset=set(e)  
        eset.remove('toDel')  
        e\[:\]=list(eset)  
    if v:  
        for t in tmp:  
            v.remove(t)  
    return tmp  
   
def topoSort(v,e):  
    result=\[\]  
    while True:  
        nodes=indegree0(v,e)  
        if nodes==None:  
            break  
        if nodes==-1:  
            print('there\\'s a circle.')  
            return None  
        result.extend(nodes)  
    return result  
   
v=\['a','b','c','d','e'\]  
e=\[('a','b'),('a','d'),('b','c'),('d','c'),('d','e'),('e','c')\]  
res=topoSort(v,e)  
print(res)

indegree0函数返回入度为0的顶点，并在v和e中删除它和它相邻的边，如果v列表中没有顶点了，就返回None，如果v列表中还有顶点但是找不到入度为0的顶点，说明有向图中有环，返回-1。topoSort函数不断取出有向图中入度为0的顶点，最后就是拓扑排序序列。输出如下：  
\['a', 'b', 'd', 'e', 'c'\]

考虑一种有环的情况，加上一条c->d的边，如下图所示：

输出如下：

there's a circle.  
None

参考文献：

[https://blog.csdn.net/littlethunder/article/details/24113193][https_blog.csdn.net_littlethunder_article_details_24113193]

[https_blog.csdn.net_littlethunder_article_details_24113193]: https://blog.csdn.net/littlethunder/article/details/24113193