Implementation (Part 2)

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

이제 순서를 구성하기 위해 진입 차수가 0인 정점들을 반복적으로 제거합니다.

챌린지

중급

이제 전체 순서를 구성해 보세요.

n과 평면화된 edges 배열(방향성 u -> v)을 인자로 받아 정점들의 위상 정렬 순서를 반환하는 topologicalSort라는 이름의 함수를 작성하세요.

Kahn의 알고리즘을 사용하세요: 진입 차수(in-degrees)를 계산한 다음, 진입 차수가 0인 정점 중 가장 작은 정점을 반복적으로 선택하여 추가하고, 해당 정점의 이웃 정점들의 진입 차수를 줄입니다. 이 챌린지의 입력값은 사이클이 없는 유향 그래프(acyclic)입니다.

매 단계에서 사용 가능한 가장 작은 정점을 선택하면 결과가 유일해집니다.

직접 해보기

#include <stdlib.h>

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

실력 점검

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

위상 정렬 - 그래프 알고리즘의 모든 레슨

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) 프로젝트 레슨

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2