隊列Queue--拓?fù)渑判?/h2>

對一個有向無環(huán)圖(Directed Acyclic Graph, DAG)G進(jìn)行拓?fù)渑判?，將G中所有頂點(diǎn)排成線性序列，使得圖中任意一對頂點(diǎn)u、v，若邊(u,v)∈E(G)，則在線性序列中u出現(xiàn)在v之前。

隊列Queue--拓?fù)渑判蚴纠?/div>

拓?fù)渑判虻姆椒ǎ?/h4>

1. 在有向圖G中任選一個沒有前驅(qū)(即入度為0)的頂點(diǎn)并輸出它；

2. 從G中刪除該頂點(diǎn)，并且刪除去從該頂點(diǎn)出發(fā)的全部有向邊；

3. 重復(fù)上述兩步，直到剩余的網(wǎng)絡(luò)中不再存在有前驅(qū)的頂點(diǎn)為止。

有向無環(huán)圖 demo

Python Demo:

# !/usr/bin/env python
# -- coding: utf-8 --
# @Time : 2017/7/10 11:46
# @Author : Albert·Sun
# @Version : 0.10α
# @Description: (1).用數(shù)組grap存放圖G的連接關(guān)系，grap[i][j]：頂點(diǎn)j指向頂點(diǎn)i,即邊E(j->i),此處邊權(quán)簡化為1; (2).Pyhton中的List結(jié)構(gòu)模擬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

注：

拓?fù)渑判虻谋举|(zhì)是不斷地輸出入度為0的點(diǎn)；

該算法可用于判斷圖中是否存在環(huán)。

最后編輯于 ：2017.12.08 16:18:32

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。