방향성 비순환 그래프의 위상 정렬 코드 예제의 Python 구현

이 문서의 내용은 Python에서 방향성 비순환 그래프의 위상 정렬에 대한 코드 예제입니다. 이는 특정 참조 값을 가지고 있으므로 도움이 될 수 있습니다.

파이썬 유향 비순환 그래프의 위상 정렬

위상 정렬의 공식 정의는 특정 집합의 부분 순서에서 집합의 전체 순서를 얻는 것입니다. 이 작업을 위상 정렬이라고 합니다. 개인적으로 위상 정렬은 그래프의 기본 순회 방법에 차수 개념을 도입하고 이를 중심으로 구현한 정렬 방법이라고 생각합니다. 토폴로지 정렬은 Python 다중 상속의 mro 규칙 정렬과 비슷합니다. C3 알고리즘에 대해 mro 규칙을 자세히 연구하고 싶다면 DAG(Directed Acylic Graph)의 토폴로지 정렬에 대해서도 배울 수도 있습니다.

In-degree: 방향성 그래프에서 노드에 대한 점 수의 합을 나타냅니다.
Directed Acylic 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가 큐에 추가된 후 큐의 헤드에서 in-degree가 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!