有向非巡回グラフのトポロジカルソートコード例の Python 実装

この記事の内容は、Python による有向非巡回グラフのトポロジカルソートのコード例に関するもので、一定の参考価値がありますので、困っている方は参考にしていただければ幸いです。

Python 有向非巡回グラフのトポロジカル ソート

トポロジカル ソートの正式な定義は次のとおりです。特定のセットの部分順序から上位部分を取得します。のセット A の合計順序、この操作はトポロジカル ソートと呼ばれます。個人的には、トポロジカルソートは、グラフの基本的な走査方法にin次数の概念を導入し、in次数を中心に実装したソート手法であると考えており、Pythonの多重継承におけるmroルールのソートに似ています。 C3 アルゴリズムについて mro ルールを詳しく学びたい場合は、DAG (有向非巡回グラフ) のトポロジカル ソートについても学ぶとよいでしょう。

次数内: 有向グラフ内のノードを指す点の合計を指します
有向非巡回グラフ: 有向非巡回グラフ、略して DAG 機械学習に精通している場合は、次のようにします。 DAG についてはよく知られていると思いますが、ANN、DNN、CNN などはすべて代表的な DAG モデルです。ここではこれらのモデルについては詳しく説明しません。興味のある方は自分で学習してください。

以下に示すように、 有向非巡回グラフ を例に挙げます。

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

A が指す要素を指します。 to は B、C
B が指す要素は D、E
C が指す要素は D、E
D が指す要素は F
E が指し、そして、指す要素はto by F
F の要素は空です
つまり、A の入次数は 0、B の入次数は 1、C の入次数は 1、D の入次数は 1 です。は 2、E の入次数は 2、F の入次数は 2
DAG のトポロジカル ソートでは、毎回、入次数が 0 のポイントが選択され、トポロジカル キューに追加されます。 、この点に接続されているすべてのエッジが削除されます。
まず、入次数が 0 の点 A を見つけて、キューから A を取り出し、結果に追加して、A に関連するポインターを削除します。つまり、B と C の入次数を 1 だけ減らします。を0にしてB、Cをキューに追加し、キューの先頭からin次数が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 中国語 Web サイトの他の関連記事を参照してください。