Python實作有向無環圖的拓樸排序程式碼範例

這篇文章帶給大家的內容是關於Python實作有向無環圖的拓樸排序程式碼範例，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

Python有向無環圖的拓樸排序

#拓樸排序的官方定義為：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓樸排序。而個人認為，拓樸排序即是在圖的基本遍歷法上引入了入度的概念並圍繞入度來實現的排序方法，拓撲排序與Python多繼承中mro規則的排序類似，若想深入研究mro規則的C3演算法，不妨了解DAG(有向無環圖) 的拓樸排序。

入度：指有向圖中某節點被指向數目總和
有向無環圖：Directed Acyclic Graph，簡稱DAG，若熟悉機器學習則肯定對DAG不陌生，如ANN 、DNN、CNN等則都是典型的DAG模型，對這類模型此處不再過多敷述，有興趣的可以自行學習。

以一個有向無環圖為例，如下圖：

#

# 定义图结构graph = {
    "A": ["B","C"],
    "B": ["D","E"],
    "C": ["D","E"],
    "D": ["F"],
    "E": ["F"],
    "F": [],}

如圖
A的指向的元素為B、C
B的指向的元素為D、E
C的指向的元素為D、E
D的指向的元素為F
E的指向的元素為F
F的指向的元素為空
即A的入度為0，B的入度為1，C的入度為1，D的入度為2，E的入度為2，F的入度為2
在DAG的拓樸排序中，每次都選取入度為0 的點加入拓樸佇列中，再刪除所有與這點連接的邊。
先找到入度為0的點A，把A從隊列中取出，同時加到結果中並把A相關的指向移除，即B、C的入度減少1變為0並將B， C加入佇列中，再從佇列首部取出入度為0的節點，以此類推，最後輸出結果，完成DAG的拓樸排序。

def TopologicalSort(G):
    # 创建入度字典
    in_degrees = dict((u, 0) for u in G)
    # 获取每个节点的入度
    for u in G:
        for v in G[u]:
            in_degrees[v] += 1
    # 使用列表作为队列并将入度为0的添加到队列中
    Q = [u for u in G if in_degrees[u] == 0]
    res = []
    # 当队列中有元素时执行
    while Q:
        # 从队列首部取出元素
        u = Q.pop()
        # 将取出的元素存入结果中
        res.append(u)
        # 移除与取出元素相关的指向，即将所有与取出元素相关的元素的入度减少1
        for v in G[u]:
            in_degrees[v] -= 1
            # 若被移除指向的元素入度为0，则添加到队列中
            if in_degrees[v] == 0:
                Q.append(v)
    return resprint(TopologicalSort(graph))

輸出結果：

['A', 'C', 'B', 'E', 'D', 'F']

程式碼輸出結果與上述分析相符

#

以上是Python實作有向無環圖的拓樸排序程式碼範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！