Implementation (Part 2)

Coddy의 크루스칼 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 6번째.

이제 MST가 완성될 때까지 가장 저렴한 안전한 간선을 추가합니다.

챌린지

중급

이제 MST를 구축해 보세요.

연결된 그래프의 n과 평면 edges 배열(트리플, 무방향)을 인자로 받아, 해당 그래프의 최소 신장 트리(Minimum Spanning Tree)의 총 가중치를 반환하는 kruskal이라는 함수를 작성하세요.

가장 저렴한 미사용 간선을 반복적으로 선택합니다. 만약 해당 간선의 끝점들이 서로 다른 집합에 있다면, 두 집합을 합치고(union) 그 가중치를 더합니다. 그렇지 않으면 해당 간선을 건너뜁니다.

이전 레슨에서 배운 union-find 개념을 재사용하세요.

직접 해보기

#include <stdlib.h>

int kruskal(int n, int* edges, int edges_size) {
    // 여기에 코드를 작성하세요
    return 0;
}

실력 점검

이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.

크루스칼 알고리즘 - 그래프 알고리즘의 모든 레슨

1Introduction

2The Algorithm

3Final Challenges