Implementation (Part 2)

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

이제 항상 가장 비용이 적은 교차 간선을 추가하며 트리를 확장합니다.

챌린지

중급

이제 전체 트리를 확장해 보세요.

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

각 정점마다 inTree 플래그를 유지하세요. 매 라운드마다 트리에 정확히 하나의 끝점만 포함된 가장 저렴한 간선을 찾아 그 가중치를 더하고, 트리에 포함되지 않았던 끝점을 트리에 추가하세요.

직접 해보기

#include <stdlib.h>

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

실력 점검

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

프림 알고리즘 - 그래프 알고리즘의 모든 레슨

1Introduction

2The Algorithm

3Final Challenges