> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/kruskal.md).

# 크루스칼(Kruskal) 알고리즘

최초작성일 \[2020.01.29]

크루스칼(Kruskal) 알고리즘은 그래프에서 [최소신장트리(Minimum Spanning Tree)](https://kde6260.gitbook.io/dev/minimum-spanning-tree)를 찾는 데 쓰이는 알고리즘이다. 

1. 각 정점을 독립된 component으로 간주한다.
2. 탐색하지 않은 간선들 중에 가중치가 가장 작은 간선 `e`로 연결된 두 정점 `v1`, `v2`가 같은 [connected component](https://kde6260.gitbook.io/dev/undefined#connected-component)에 있는지 확인한다.
3. 같은 connected component에 있지 않으면 `e`를 집합 `X`에 추가하고 `v1`, `v2`를 같은 disjoint set으로 묶는다.
4. 같은 connected component에 있으면 `e`는 사이클을 만드는 간선이므로 `X`에 추가하지 않는다.
5. 모든 정점이 1개의 disjoint set으로 묶일 때까지 2 \~ 4 를 반복한다.

![](/files/-Lzlc78-qZM4WkM5JCVU)

의사코드는 아래와 같다.

```python
def kruskal(G):
  X = set()

  for each v in V:
    make_set(v)
  
  E = sort_E_by_weight(E)  # 1
 
  for each (v1, v2) in E:
    if find(v1) != find(v2):  # 2
      X.add((v1, v2))
      union(v1, v2)  # 3
  
  return X
```

**시간복잡도**

시간복잡도를 계산하기 위해 의사코드에서 매긴 번호로 로직을 분류한다.

1. 간선을 정렬하는 데 걸리는 시간복잡도는 퀵정렬을 사용한다면 `O(|E|log|E|)` 이다.
2. 각 간선을 순회하면서 `find()`를 2번 실행하므로 `O(log|V|)`이다. (트리형태의 disjoint set에서 어떤 노드의 루트를 찾는 데 걸리는 시간복잡도는 `O(log|V|)`이기 때문.) 
3. `union()`은 heuristic rank를 적용하면 `O(1)`이다. (`find()`를 호출하면서 `v1`, `v2`의 루트가 이미 갱신되었기 때문.)

따라서 `|E| * log|E| + |E|(log|V| + 1)` = `|E| * (log|E| + log|V|)` 가 된다. 그런데 최신장트리는 모든 정점이 연결되어야 함을 가정하므로 그래프 내 간선의 갯수는 적어도 `|V| - 1` 개 이상이다. 따라서 크루스칼 알고리즘의 시간복잡도는 최종적으로 

`|E| * (log|E| + log(|E|+1)}` = `O(|E|log|E|)` 가 된다. 


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kde6260.gitbook.io/dev/kruskal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.