拓撲排序是對有向無環(huán)圖（DAG）進行排序的一種算法，它可以將圖中的頂點排成一個線性序列，使得圖中的任意一條有向邊都從序列中的較早頂點指向較晚頂點。換句話說，如果圖中存在一條從頂點A到頂點B的有向邊，那么在拓撲排序中頂點A一定出現(xiàn)在頂點B之前。

統(tǒng)計入度：
對圖中的每個頂點，統(tǒng)計其入度，即指向它的邊的數(shù)量。
初始化：
將入度為0的頂點加入一個隊列，作為初始節(jié)點。
拓撲排序：
1.從隊列中取出一個頂點，并輸出。
2.將該頂點的所有鄰接頂點的入度減1。
3.如果某個鄰接頂點的入度減為0，則將其加入隊列。
4.重復步驟3，直到隊列為空。
檢查：
如果輸出的頂點數(shù)等于圖中的頂點數(shù)，則拓撲排序成功，否則圖中存在環(huán)。
假設有以下有向圖：

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

首先統(tǒng)計每個頂點的入度：
1號頂點入度為0
2號頂點入度為1
3號頂點入度為1
4號頂點入度為1
5號頂點入度為2
6號頂點入度為1
將入度為0的頂點加入隊列：[1]

開始拓撲排序：
取出隊列中的1號頂點，并輸出：1
將1號頂點的鄰接頂點2號和3號的入度分別減1，得到入度為0的2號和3號頂點，加入隊列：[2, 3]
取出隊列中的2號頂點，并輸出：2
將2號頂點的鄰接頂點4號的入度減1，得到入度為0的4號頂點，加入隊列：[3, 4]
取出隊列中的3號頂點，并輸出：3
將3號頂點的鄰接頂點5號的入度減1，得到入度為1的5號頂點，加入隊列：[4, 5]
取出隊列中的4號頂點，并輸出：4
將4號頂點的鄰接頂點6號的入度減1，得到入度為0的6號頂點，加入隊列：[5, 6]
取出隊列中的5號頂點，并輸出：5
取出隊列中的6號頂點，并輸出：6
完成拓撲排序，輸出結果為：[1, 2, 3, 4, 5, 6]。

from collections import defaultdict, deque

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

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

sorted_nodes = topological_sort(graph)
if sorted_nodes:
    print("拓撲排序結果:", sorted_nodes)
else:
    print("圖中存在環(huán)，無法進行拓撲排序")

統(tǒng)計入度：
遍歷圖中的每個節(jié)點，統(tǒng)計每個節(jié)點的入度，即指向該節(jié)點的邊的數(shù)量。
初始化：
將入度為0的節(jié)點加入一個隊列，作為拓撲排序的初始節(jié)點。
拓撲排序：
1.從隊列中取出一個節(jié)點，并輸出到結果列表中。
2.將該節(jié)點的所有鄰接節(jié)點的入度減1。
3.如果某個鄰接節(jié)點的入度減為0，則將其加入隊列。
4.重復上述步驟直到隊列為空。
檢查：
如果結果列表中的節(jié)點數(shù)等于圖中的節(jié)點數(shù)，則拓撲排序成功，否則圖中存在環(huán)。

到此這篇關于python實現(xiàn)拓撲排序的方法步驟的文章就介紹到這了,更多相關python 拓撲排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論