크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘입니다. ​ ※ 신장 트리 : 그래프 내의 모든 노드를 포함하는 트리 노드 = 정점 = 도시 : 그래프에서 동그라미에 해당하는 부분 간선 = 거리 = 비용 : 그래프에서 선에 해당하는 부분 ​ 위 그래프를 살펴보았을 때 6개의 노드와 8개의 간선이 있습니다. 해당 그래프를 크루스 칼 알고리즘을 적용시켜 본다면 아래와 같습니다. ​ 잠시 그래프에서 모든 노드를 연결하기 위해 최소한으로 필요한 간선의 수는 N( 노드) - 1개입니다. 즉 위 그래프는 노드가 6개 있으므로 최소 비용 신장 트리를 만들기 위해 필요한 간선의 수는 5개입니다. ​ 일단 모든 노드를 최대한 적은 ..

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