CH14-4 최소 비용 신장 트리(3)
이번시간에는 크루스칼 알고리즘을 구현해보겠다.
자료구조의 마지막 강의이다…
이론적인건 전에 설명 다 했다.
마지막 강의라서 그런지.. 한마디 해주신다. 지금까지 우리가 많은 자료구조 및 알고리즘들도 구현했다. 사실 지금까지 구현했던 대상들은 처음부터 구현하려면 어렵게 느껴지는게 맞다. 하지만 우리는 기존에 만들었던 자료구조들을 활용해서 그것들을 기반으로 새로운 구조를 구현하는 방법을 채택했었다.
이런 프로그래밍 방식을 앞으로 잊지 말길 바란다. C든 다른 언어든, 우리가 했던 것 처럼 헤더파일을 디자인하면서 프로그래밍한다면, 프로그래밍의 재미를 느낄 수 있을 것이다.
크루스칼 알고리즘을 다음과 같이 구현할 것이다.
가중치를 기준으로, 간선을 내림 차순으로 정렬한 다음 높은 가중치의 간선부터 시작해서 하나씩 그래프를 제거하는 방식.
앞에서 구현했던 DFS를 재활용 할 것이다. 가중치가 포함된 간선을 표현한 구조체가 새로 정의되어야 하므로, 새로운 헤더도 하나 필요하다.
이론적으로 살펴본 크루스칼 알고리즘에선, 다음의 질문에 답을 할 필요가 있었다. - 어떤 간선을 제거하면, 해당 간선에 원래 연결되어있었던 정점이 독립된 정점이 되어버리지 않는가?(혹은 어떤 간선을 추가하면, 해당 간선이 사이클을 형성하는가?)
위의 질문에 대답할 헬퍼펑션을 하나 제작해야 한다. 이는 전에 구현한 DFShowGraphVertex()함수를 확장시켜 만들 수 있다. DFShowGraphVertex()덕분에 우리는 한 시작정점으로부터 모든 정점을 다 방문할 수 있는 능력이 이미 있다. 모든 정점을 방문하되, 인자로 들어간 어떤 정점을 방문하지 않았다면 그 정점은 독립된 정점이라고 판단할 수 있다.