이전 포스팅에서 Kruskal 알고리즘에 대해서 알아보았음. [파이썬 자료구조] Kruskal 알고리즘 [파이썬 자료구조] 그래프(Graph) 그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간� ohaengsa.tistory.com Kruskal 알고리즘에서 cycle 여부를 확인하는 과정임. 정점X와 정점Y를 직접 연결하려할 때 정점X에서 Y로 가는 경로가 이미 존재하는지 확인하는 방법 만약 X,Y가 Z를 통해 연결되어있다면 X,Y를 직접 연결하는 edge를 버림 자기 자신을 가르키는 하나의 원소로 이루어짐 5개의 집합있다고 가정함. {0}과 {1}을 합치면 1은 0을 가르킨다. 왼쪽 ..

[파이썬 자료구조] 그래프(Graph) 그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간선에 가중치가 부여된 그래프 병 ohaengsa.tistory.com 최소신장트리(MST)는 edge의 가중치의 합이 최소인 신장트리임 신장트리란? 모든 정점을 연결하는 트리라고 생각하면됨. Kruskal 알고리즘 가중치의 크기순서대로 간선을 추가하며, 싸이클이 만들지 않는 알고리즘임 최소신장트리(MST)를 만드는 알고리즘 예제를 보면 7개의 정점과 12개의 edge가 있음. 각각의 edge에는 가중치가 있음. 0단계. edge를 가중치에 따라 정렬을 함 1단계. 정렬순서대로 (4,6)을 연결하는 ed..