欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實(shí)現(xiàn)拓?fù)渌惴ǖ氖纠?/h1>
 更新時間：2023年05月30日 09:51:29   作者：福州司馬懿  
本文主要介紹了Python實(shí)現(xiàn)拓?fù)渌惴ǖ氖纠?，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

前言

拓?fù)渑判蚴菆D論中一種重要的排序算法，用于對有向無環(huán)圖（DAG）進(jìn)行排序。在拓?fù)渑判蛑?，圖的頂點(diǎn)表示任務(wù)，有向邊表示任務(wù)之間的依賴關(guān)系。拓?fù)渑判蛩惴梢哉业揭环N滿足所有任務(wù)依賴關(guān)系的順序。

算法原理

拓?fù)渑判蛩惴ǖ幕驹砣缦拢?/p>

  • 創(chuàng)建一個空的排序結(jié)果列表。
  • 找到圖中所有入度為0的頂點(diǎn)（即沒有依賴關(guān)系的頂點(diǎn)），將其加入排序結(jié)果列表。
  • 移除該頂點(diǎn)以及與其相關(guān)的邊。
  • 重復(fù)步驟2和3，直到圖中的所有頂點(diǎn)都被處理。
  • 如果排序結(jié)果列表的長度等于圖中的頂點(diǎn)數(shù)，則拓?fù)渑判虺晒?；否則，圖中存在環(huán)，無法進(jìn)行拓?fù)渑判颉?/li>

Python實(shí)現(xiàn)

下面是使用Python實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ氖纠a：

from collections import deque
def topological_sort(graph):
? ? # 統(tǒng)計每個頂點(diǎn)的入度
? ? in_degree = {v: 0 for v in graph}
? ? # 計算每個頂點(diǎn)的入度
? ? for v in graph:
? ? ? ? for neighbor in graph[v]:
? ? ? ? ? ? in_degree[neighbor] += 1
? ? # 將入度為0的頂點(diǎn)加入隊(duì)列
? ? queue = deque([v for v in graph if in_degree[v] == 0])
? ? # 保存拓?fù)渑判虻慕Y(jié)果
? ? result = []
? ? while queue:
? ? ? ? # 取出隊(duì)列中的頂點(diǎn)
? ? ? ? v = queue.popleft()
? ? ? ? result.append(v)
? ? ? ? # 移除頂點(diǎn)及其相關(guān)邊
? ? ? ? for neighbor in graph[v]:
? ? ? ? ? ? in_degree[neighbor] -= 1
? ? ? ? ? ? if in_degree[neighbor] == 0:
? ? ? ? ? ? ? ? queue.append(neighbor)
? ? # 判斷是否存在環(huán)
? ? if len(result) != len(graph):
? ? ? ? raise ValueError("圖中存在環(huán)，無法進(jìn)行拓?fù)渑判颉?)
? ? return result
# 測試
graph = {
? ? 'A': ['B', 'C'],
? ? 'B': ['D'],
? ? 'C': ['D', 'E'],
? ? 'D': ['F'],
? ? 'E': ['F'],
? ? 'F': []
}
try:
? ? result = topological_sort(graph)
? ? print("拓?fù)渑判蚪Y(jié)果:", result)
except ValueError as e:
? ? print(e)

以上代碼中，graph表示圖的鄰接表表示法，其中每個頂點(diǎn)表示為一個鍵，其對應(yīng)的值為一個列表，列表中存儲了與該頂點(diǎn)有直接邊相連的頂點(diǎn)。

運(yùn)行代碼后，將輸出拓?fù)渑判虻慕Y(jié)果。

這就是使用Python實(shí)現(xiàn)拓?fù)渑判蛩惴ǖ氖纠a。通過這個算法，我們可以對有向無環(huán)圖進(jìn)行

排序，找到滿足任務(wù)依賴關(guān)系的順序。

到此這篇關(guān)于Python實(shí)現(xiàn)拓?fù)渌惴ǖ氖纠奈恼戮徒榻B到這了,更多相關(guān)Python 拓?fù)渌惴▋?nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論