Python implementation of topological sorting code example of directed acyclic graph

The content of this article is about the code example of topological sorting of directed acyclic graph in Python. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Topological sorting of Python directed acyclic graph

The official definition of topological sorting is: from a partial order on a certain set to get the upper part of the set A total order of , this operation is called topological sorting. Personally, I believe that topological sorting is a sorting method that introduces the concept of in-degree into the basic traversal method of graphs and implements it around in-degree. Topological sorting is similar to the sorting of mro rules in Python multiple inheritance. If you want to study the mro rules in depth C3 algorithm, you might as well learn about the topological sorting of DAG (Directed Acyclic Graph).

In-degree: refers to the sum of the number of points pointed to a node in the directed graph
Directed Acyclic Graph: Directed Acyclic Graph, DAG for short. If you are familiar with machine learning, you will definitely be familiar with DAG, such as ANN , DNN, CNN, etc. are all typical DAG models. I won’t elaborate too much on these models here. Those who are interested can learn by themselves.

Take a directed acyclic graph as an example, as shown below:

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

A points to The element pointed to is B, the element pointed to by C
B is D, the element pointed to by E
C is D, the element pointed to by E
D is pointed to by F
E, and the element pointed to by F
F The element of is empty
That is, the in-degree of A is 0, the in-degree of B is 1, the in-degree of C is 1, the in-degree of D is 2, the in-degree of E is 2, and the in-degree of F is 2
In the topological sorting of DAG, each time a point with an in-degree of 0 is selected and added to the topological queue, and then all edges connected to this point are deleted.
First find the point A with an in-degree of 0, take A out of the queue, add it to the result and remove the pointers related to A, that is, reduce the in-degrees of B and C by 1 to 0 and add B, C is added to the queue, and then the node with an in-degree of 0 is taken out from the head of the queue, and so on, and finally the result is output to complete the topological sorting of the 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))

Output results:

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

The code output results are consistent with the above analysis

The above is the detailed content of Python implementation of topological sorting code example of directed acyclic graph. For more information, please follow other related articles on the PHP Chinese website!