拓?fù)渑判蚴菍?duì)有向無(wú)環(huán)圖（DAG）進(jìn)行排序的一種算法，它可以將圖中的頂點(diǎn)排成一個(gè)線性序列，使得圖中的任意一條有向邊都從序列中的較早頂點(diǎn)指向較晚頂點(diǎn)。換句話說(shuō)，如果圖中存在一條從頂點(diǎn)A到頂點(diǎn)B的有向邊，那么在拓?fù)渑判蛑许旤c(diǎn)A一定出現(xiàn)在頂點(diǎn)B之前。

統(tǒng)計(jì)入度：
對(duì)圖中的每個(gè)頂點(diǎn)，統(tǒng)計(jì)其入度，即指向它的邊的數(shù)量。
初始化：
將入度為0的頂點(diǎn)加入一個(gè)隊(duì)列，作為初始節(jié)點(diǎn)。
拓?fù)渑判颍?br />1.從隊(duì)列中取出一個(gè)頂點(diǎn)，并輸出。
2.將該頂點(diǎn)的所有鄰接頂點(diǎn)的入度減1。
3.如果某個(gè)鄰接頂點(diǎn)的入度減為0，則將其加入隊(duì)列。
4.重復(fù)步驟3，直到隊(duì)列為空。
檢查：
如果輸出的頂點(diǎn)數(shù)等于圖中的頂點(diǎn)數(shù)，則拓?fù)渑判虺晒?，否則圖中存在環(huán)。
假設(shè)有以下有向圖：

 1  →  2  →  4
 ↓  ↗ ↓  ↗ ↓
 3    5  →  6

首先統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度：
1號(hào)頂點(diǎn)入度為0
2號(hào)頂點(diǎn)入度為1
3號(hào)頂點(diǎn)入度為1
4號(hào)頂點(diǎn)入度為1
5號(hào)頂點(diǎn)入度為2
6號(hào)頂點(diǎn)入度為1
將入度為0的頂點(diǎn)加入隊(duì)列：[1]

開始拓?fù)渑判颍?br />取出隊(duì)列中的1號(hào)頂點(diǎn)，并輸出：1
將1號(hào)頂點(diǎn)的鄰接頂點(diǎn)2號(hào)和3號(hào)的入度分別減1，得到入度為0的2號(hào)和3號(hào)頂點(diǎn)，加入隊(duì)列：[2, 3]
取出隊(duì)列中的2號(hào)頂點(diǎn)，并輸出：2
將2號(hào)頂點(diǎn)的鄰接頂點(diǎn)4號(hào)的入度減1，得到入度為0的4號(hào)頂點(diǎn)，加入隊(duì)列：[3, 4]
取出隊(duì)列中的3號(hào)頂點(diǎn)，并輸出：3
將3號(hào)頂點(diǎn)的鄰接頂點(diǎn)5號(hào)的入度減1，得到入度為1的5號(hào)頂點(diǎn)，加入隊(duì)列：[4, 5]
取出隊(duì)列中的4號(hào)頂點(diǎn)，并輸出：4
將4號(hào)頂點(diǎn)的鄰接頂點(diǎn)6號(hào)的入度減1，得到入度為0的6號(hào)頂點(diǎn)，加入隊(duì)列：[5, 6]
取出隊(duì)列中的5號(hào)頂點(diǎn)，并輸出：5
取出隊(duì)列中的6號(hào)頂點(diǎn)，并輸出：6
完成拓?fù)渑判?，輸出結(jié)果為：[1, 2, 3, 4, 5, 6]。

from collections import defaultdict, deque

def topological_sort(graph):
    # 統(tǒng)計(jì)入度
    indegree = defaultdict(int)
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1
    
    # 將入度為0的節(jié)點(diǎn)加入隊(duì)列
    queue = deque([node for node in graph if indegree[node] == 0])
    result = []
    
    # 拓?fù)渑判?
    while queue:
        node = queue.popleft()
        result.append(node)
        # 將該節(jié)點(diǎn)的鄰接節(jié)點(diǎn)的入度減1，并將入度為0的節(jié)點(diǎn)加入隊(duì)列
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    # 如果結(jié)果中的節(jié)點(diǎn)數(shù)等于圖中的節(jié)點(diǎn)數(shù)，則拓?fù)渑判虺晒?
    if len(result) == len(graph):
        return result
    else:
        return None

# 測(cè)試
graph = {
    '1': ['2', '3'],
    '2': ['4', '5'],
    '3': ['5'],
    '4': ['6'],
    '5': ['6'],
    '6': []
}

sorted_nodes = topological_sort(graph)
if sorted_nodes:
    print("拓?fù)渑判蚪Y(jié)果:", sorted_nodes)
else:
    print("圖中存在環(huán)，無(wú)法進(jìn)行拓?fù)渑判?)

統(tǒng)計(jì)入度：
遍歷圖中的每個(gè)節(jié)點(diǎn)，統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度，即指向該節(jié)點(diǎn)的邊的數(shù)量。
初始化：
將入度為0的節(jié)點(diǎn)加入一個(gè)隊(duì)列，作為拓?fù)渑判虻某跏脊?jié)點(diǎn)。
拓?fù)渑判颍?br />1.從隊(duì)列中取出一個(gè)節(jié)點(diǎn)，并輸出到結(jié)果列表中。
2.將該節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)的入度減1。
3.如果某個(gè)鄰接節(jié)點(diǎn)的入度減為0，則將其加入隊(duì)列。
4.重復(fù)上述步驟直到隊(duì)列為空。
檢查：
如果結(jié)果列表中的節(jié)點(diǎn)數(shù)等于圖中的節(jié)點(diǎn)數(shù)，則拓?fù)渑判虺晒Γ駝t圖中存在環(huán)。

到此這篇關(guān)于python實(shí)現(xiàn)拓?fù)渑判虻姆椒ú襟E的文章就介紹到這了,更多相關(guān)python 拓?fù)渑判騼?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論