Algorithm
greedy알고리즘 에 속하며 union-find와 연관이있어서 대장찾기에대해서 이해해야 크루스칼에대해서
이해가 가능한것같다 비전공자인 내게는 그래프라는게 이해하는데 한참 걸렸다 내가 아는건 차트밖에없었으니
그냥 단순하게 그래프=차트 라고 머릿속에 박혀있어서 이 개념을 깨고 이해하는데 애좀 먹었다.
신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데,
대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다.
크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.
크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다.
최소신장 트리가 뭘까? (minimum spanning tree)
신장트리란 어떤 그래프가있을때 각 노드를 모두 포함하면서 싸이클이 존재하지 않는 그래프를 의미한다.
-> 이때 모든 노드를 포함하며 서로 연결되어있지만 사이클이 존재하지않는 조건은
트리의 성립조건이기도하다 트리와 그래프가 따로 있는게 아닌 그래프 분류안에
트리가 있기때문이다. 싸이클이 없이 모든노드를 이을수만있다면 그것이 곧 spanning tree 인것이다.
따라서 최소 신장트리는 간선의 가중치가 있을때 각 노드를 포함하면서 싸이클이 없는 그래프인데 각 간선들의
총합이 가장 작은 트리를 지칭하는것이다.
동작 원리를 알아보자
다른 블로그들을 봤지만 이해하기 힘들어서 문제를 풀어보면서 감이왔는데
보통 그래프를 나타날때는 인접행렬이나 인접리스트로 표현하게되는데
개인적으로 인접리스트가 좀더 편하기 때문에 인접리스트로 설명하겠다.
인접리스트로 그래프를 표현하면 보통 이런식으로 표현이 될것이다
[
[from,to,cost],
[from,to,cost],
[from,to,cost],
[from,to,cost]
]여기서 중요한과정인 cost 기준으로 오름차순 정렬이 필요하다.
그런후 그래프를 순회하면서 find(from) === find(to)로 연결이 되어있는지 확인해주고
연결이 되어있지않으면 union으로 합쳐준후 cost를 저장해준다.
이해하고나니 그렇게 어렵진않은데 개고생을 좀 한것같다.
