spanning tree

유니온-파인드(Union-Find)? Union-Find는 여러 개의 노드가 존재할 때, 어떤 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 방법 같은 그래프에 속하는지 어떻게 판별할까? 다음 그림을 보고 쉽게 이해하자 먼저 8개의 노드가 위와 같이 있다고 가정한다. 각 노드는 자기 자신을 가리키며 이는 자기 자신이 곧 루트 노드임을 의미한다. 여기서 5와 2가 연결되었다고 해보자. 그럼 다음과 같이 표현할 수 있다. 5번 노드에 2번 노드를 가리키는 값 2가 들어간다. 일반적으로 합칠 때는 더 작은쪽으로 합치며 이를 Union이라 한다. 그 다음 2와 1이 연결되었다고 해보자. 2번 노드는 1번 노드를 가리키며 이를 의미하는 값 1이 들어간다. 그럼 여기서 5번과 1번이 같은 그래프에 속하는..

신장 트리(Spanning Tree)? Spanning Tree는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 특징 DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 최소 신장 트리(MST, Minimum Spanning Tre..