亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

前言

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

算法原理

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

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

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

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

from collections import deque
def topological_sort(graph):
? ? # 統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度
? ? in_degree = {v: 0 for v in graph}
? ? # 計(jì)算每個(gè)頂點(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)，無(wú)法進(jìn)行拓?fù)渑判颉?)
? ? return result
# 測(cè)試
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表示圖的鄰接表表示法，其中每個(gè)頂點(diǎn)表示為一個(gè)鍵，其對(duì)應(yīng)的值為一個(gè)列表，列表中存儲(chǔ)了與該頂點(diǎn)有直接邊相連的頂點(diǎn)。

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

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

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

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

相關(guān)文章

最新評(píng)論