최소 신장 트리? 신장 트리란 그래프 내에 모든 정점을 포함하는 최소 연결 그래프이다. 최소 신장 트리가 되려면 아래 조건을 만족해야한다. - 최소한의 간선으로 모든 정점이 연결되어야 한다. - 모든 신장 트리 중 가중치의 값이 최소여야 한다. - Cycle이 발생해서는 안된다. 최소 신장 트리를 구현하기 위한 대표적인 알고리즘이 크루스칼 알고리즘이다. 크루스칼 알고리즘? 그리디 개념을 이용해서 구현할 수 있다. 모든 그래프를 부분 집합으로 분리하고 가중치가 낮은 간선을 선택해 연결한다. 이때 Cycle이 발생하지 않도록 주의한다. => Cycle을 판단하기 위해서 Union-Find 알고리즘을 이용한다. Union-Find 알고리즘? 공통 원소가 없는 두 집합을 구하기 위한 알고리즘이다. 서로 다른 두..

Union-Find ( 합집합 찾기) : 대표적인 그래프 알고리즘. 서로소 집합( Disjoint-Set) 알고리즘이라고도 한다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여, 현재 두 노드가 같은 그래프에 속하는지 판별 -> Find와 Union 연산을 수행할 수 있다. ​ 위와 같이 여러 개의 노드가 자유분방하게 존재하고 있다고 했을 때, 이들은 모두 연결되지 않고 각자 자신만을 집합의 원소로 가지고 있을 때 아래와 같이 표현할 수 있다. 모든 값은 자기 자신을 부모 노드로 가지고 있습니다. 이때, 위와 같이 1과 2가 연결되었을 때, 표로 표현하였을 때 아래의 표로 나타납니다. 노드 번호 1 2 3 4 5 6 7 부모 노드 번호 1 1 3 4 5 6 7 2번째 인덱스의 값에 ' 1 ' 이 ..