[파이썬/Python] 최소 비용 신장 트리 알고리즘 작동원리 이해하기 ( Prim / Kruskal )

최소 비용 신장 트리 알고리즘 작동원리 이해하기 ( Prim / Kruskal )

---

서론

[파이썬/Python] 최소 비용 신장 트리 알고리즘 구현하기 ( Prim / Kruskal )

이전 시간 구현하였던 Prim, Kruskal 알고리즘의 작동원리에 대해 간단한 예제를 통해 그림으로 이해해보려고 합니다.

---

본론

문제 1. Prim 알고리즘을 이용하여 위 그래프의 최소비용 신장 트리를 구하는 과정을 제시하시오.

 

 

처음 start_node = 1이므로, d[1] = 0 이 저장됩니다.

나머지 노드들은 무한으로 초기화했기 때문에 무한대가 담겨 있습니다.

 

def extract_min(self, V_minus_S, d):
    min = sys.maxsize
    selected_node = None
    
    for node in V_minus_S: # 트리 외부 노드들을 비교
        if d[node] < min: # d 값이 가장 작다면
            min = d[node] # d 값으로 저장
            selected_node = node # 최소 가중치 간선 노드
    
    return selected_node

이전에 작성했던 코드 중 인접 노드에서 가중치가 가장 작은 노드를 반환해주는 함수입니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 1이고, d[1] = 0 입니다.

인접 노드들의 가중치가 d[인접노드] 에 저장된 것을 확인할 수 있습니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 4이고, d[4] = 17 입니다.

인접 노드들의 가중치가 d[인접노드] 에 저장된 것을 확인할 수 있습니다.

 

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 8이고, d[8] = 17 입니다.

인접 노드들의 가중치가 d[인접노드] 에 저장된 것을 확인할 수 있습니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 9이고, d[9] = 17 입니다.

인접 노드들의 가중치가 d[인접노드] 에 저장된 것을 확인할 수 있습니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 5이고, d[5] = 10 입니다.

인접 노드들의 가중치가 d[인접노드] 에 저장된 것을 확인할 수 있습니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 10이고, d[10] = 12 입니다.

인접 노드들의 가중치가 d[인접노드] 에 저장된 것을 확인할 수 있습니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 6이고, d[6] = 6 입니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 3이고, d[3] = 18 입니다.

인접 노드들의 가중치가 d[인접노드] 에 새롭게 갱신된 것을 확인할 수 있습니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 7이고, d[7] = 5 입니다.

 

extract_min 함수를 통해 반환된 최소 가중치 노드는 2이고, d[2] = 32 입니다.

 

prim 알고리즘을 통해 완성된 최소 비용 신장 트리입니다.

---

 

문제 2. Kruskal 알고리즘을 이용하여 위 그래프의 최소비용 신장 트리를 구하는 과정을 제시하시오.

 

크루스칼 알고리즘은 시작 정점이 없기 때문에 처음 그래프가 그대로 주어집니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=3)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=4)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=5)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=6)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=10)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=12)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=17)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=18)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

가중치가 제일 작은 간선을 꺼냅니다.(=25)

그러나, 두 정점이 같은 집합에 속하므로 아무 일도 일어나지 않습니다.

 

그 다음 가중치가 제일 작은 간선을 꺼냅니다.(=28)

그러나, 두 정점이 같은 집합에 속하므로 아무 일도 일어나지 않습니다.

 

그 다음 가중치가 제일 작은 간선을 꺼냅니다.(=45)

두 정점이 서로 다른 집합에 속하므로, 하나로 합칩니다.

 

kruskal 알고리즘을 통해 완성된 최소 비용 신장 트리입니다.

---

if __name__ == "__main__":
    adjacency_list = {
        '1': {'2': 32, '4': 17},
        '2': {'1': 32, '5': 45},
        '3': {'4': 18, '7': 5},
        '4': {'1': 17, '3': 18, '5': 10, '8': 3},
        '5': {'2': 45, '4': 10, '6': 28, '9': 25},
        '6': {'5': 28, '10': 6},
        '7': {'3': 5, '8': 59},
        '8': {'4': 3, '7': 59, '9': 4},
        '9': {'5': 25, '8': 4, '10': 12},
        '10': {'6': 6, '9': 12}
    }

그래프를 제대로 그렸는지 확인하기 위해 지난번 작성한 코드에서 딕셔너리를 수정하여 컴파일해보았습니다.

 

출력 결과 직접 그려본 그래프와 코드의 결과가 일치함을 확인할 수 있었습니다.

---

결론

지난 시간 프림 알고리즘과 크루스칼 알고리즘의 코드를 작성해보면서, 알고리즘의 원리에 대해 이해하였다.

이번 시간 그 알고리즘의 작동 원리를 그림을 통해 그려보면서 보다 자세하게 알고리즘의 작동 원리에 대해 이해하는 시간을 가질 수 있었다.

특히 직접 그림을 그리며 알고리즘의 작동 원리를 확인해보는게 훨씬 빠르고 쉽게 알고리즘을 이해할 수 있는 것 같다.