[Python] 욕심 알고리즘 - prim - 과 - Kruskal 구현 - 최소 생 성 트 리

목표.
연결 망 의 모든 생 성 트 리 에서 모든 변 의 대가 와 가장 작은 생 성 트 리 를 찾 아 최소 생 성 트 리 문제 라 고 부른다. (간단하게 말 하면 AOV 망 에서 n 개의 정점 대 가 를 연결 하 는 총 과 가장 작은 변 집 을 찾 는 것 이다.)
최소 생 성 트 리 의 두 가지 알고리즘, Prim 과 Kruskal 을 기록 합 니 다.
Prim 알고리즘 사고방식

임의의 정점 에서 시작 하여 매번 현재 정점 과 가장 가 까 운 정점 을 선택 하고 두 점 사이 의 변 을 나무 에 넣는다

선 택 된 점 은 하나의 집합 을 구성 하고 나머지 는 후보 집

이다.

매번 선택 한 점 의 집합 에서 비용 이 가장 적은 점 을 찾 아 가입

동시에 후보 에서 집중 적 으로 삭제

3 과 4 를 반복 해 후보 집중 에 원소 가 없다 는 것 을 알 았 다.

Prim 알고리즘 코드

def cmp(key1, key2):
    return (key1, key2) if key1 < key2 else (key2, key1)


def prim(graph, init_node):
    visited = {init_node}
    candidate = set(graph.keys())
    candidate.remove(init_node)  # add all nodes into candidate set, except the start node
    tree = []

    while len(candidate) > 0:
        edge_dict = dict()
        for node in visited:  # find all visited nodes
            for connected_node, weight in graph[node].items():  # find those were connected
                if connected_node in candidate:
                    edge_dict[cmp(connected_node, node)] = weight
        edge, cost = sorted(edge_dict.items(), key=lambda kv: kv[1])[0]  # find the minimum cost edge
        tree.append(edge)
        visited.add(edge[0])  # cause you dont know which node will be put in the first place
        visited.add(edge[1])
        candidate.discard(edge[0]) # same reason. discard wont raise an exception.
        candidate.discard(edge[1])
    return tree


if __name__ == '__main__':
    graph_dict = {
        "A": {"B": 7, "D": 5},
        "B": {"A": 7, "C": 8, "D": 9, "E": 5},
        "C": {"B": 8, "E": 5},
        "D": {"A": 5, "B": 9, "E": 15, "F": 6},
        "E": {"B": 7, "C": 5, "D": 15, "F": 8, "G": 9},
        "F": {"D": 6, "E": 8, "G": 11},
        "G": {"E": 9, "F": 11}
    }

    path = prim(graph_dict, "D")
    print(path)  # [('A', 'D'), ('D', 'F'), ('A', 'B'), ('B', 'E'), ('C', 'E'), ('E', 'G')]

Prim 알고리즘 이 그림 에 주목 하 는 점 과 달리 Kruskal 알고리즘 은 그림 의 가장자리 에 더 관심 을 가 집 니 다.
Kruskal 알고리즘 사고방식

먼저 그림 의 모든 변 을 점차적으로 정렬 하고 정렬 기준 은 각 변 의 가중치

이다.

각 변 을 차례대로 옮 겨 다 니 며 이 변 을 넣 은 후에 도형 을 고리 로 만 들 지 않 으 면 넣 고 그렇지 않 으 면 포기 합 니 다

Kruskal 알고리즘 은 생각 이 뚜렷 해 보이 지만 그림 에 고리 가 있 는 지 아 닌 지 를 어떻게 판단 하 는 지 이해 하기 어렵다.
Kruskal 알고리즘 코드

def cmp(key1, key2):
    return (key1, key2) if key1 < key2 else (key2, key1)


def find_parent(record, node):
    if record[node] != node:
        record[node] = find_parent(record, record[node])
    return record[node]


def naive_union(record, edge):
    u, v = find_parent(record, edge[0]), find_parent(record, edge[1])
    record[u] = v


def kruskal(graph, init_node):
    edge_dict = {}
    for node in graph.keys():
        edge_dict.update({cmp(node, k): v for k, v in graph[node].items()})
    sorted_edge = list(sorted(edge_dict.items(), key=lambda kv: kv[1]))
    tree = []
    connected_records = {key: key for key in graph.keys()}

    for edge_pair, _ in sorted_edge:
        if find_parent(connected_records, edge_pair[0]) != \
                find_parent(connected_records, edge_pair[1]):
            tree.append(edge_pair)
            naive_union(connected_records, edge_pair)
    return tree


if __name__ == '__main__':
    graph_dict = {
        "A": {"B": 7, "D": 5},
        "B": {"A": 7, "C": 8, "D": 9, "E": 5},
        "C": {"B": 8, "E": 5},
        "D": {"A": 5, "B": 9, "E": 15, "F": 6},
        "E": {"B": 7, "C": 5, "D": 15, "F": 8, "G": 9},
        "F": {"D": 6, "E": 8, "G": 11},
        "G": {"E": 9, "F": 11}
    }

    path = kruskal(graph_dict, "D")
    print(path)  # [('A', 'D'), ('D', 'F'), ('A', 'B'), ('B', 'E'), ('C', 'E'), ('E', 'G')]

참고 문장

그림 옮 겨 다 니 기 알고리즘 의 최소 생 성 트 리 Prim 알고리즘 과 Kruskal 알고리즘)

도 론 (6): 그림 의 최소 생 성 트 리 문제 - Prim 과 Kruskal 알고리즘

링 으로 판단

Kruskal 과 Prim 이라는 두 가지 최소 생 성 트 리 알고리즘 (Python 구현)

에 대해 이야기 합 니 다.