Implementacja (część 2)

Lekcja 6 z 9 w kursie Sortowanie topologiczne – algorytmy grafowe w Coddy.

Teraz wielokrotnie usuwamy wierzchołki o stopniu wejściowym równym 0, aby utworzyć kolejność.

Wyzwanie

Średni

Teraz zbuduj pełne uporządkowanie.

Napisz funkcję o nazwie topologicalSort, która przyjmuje n i płaską tablicę edges (skierowane u -> v) oraz zwraca porządek topologiczny wierzchołków.

Użyj algorytmu Kahna: oblicz stopnie wejściowe, a następnie wielokrotnie wybieraj najmniejszy wierzchołek o stopniu wejściowym równym 0, dodawaj go do wyniku i zmniejszaj stopnie wejściowe jego sąsiadów wychodzących. Dane wejściowe tego wyzwania nie zawierają cykli.

Wybieranie najmniejszego dostępnego wierzchołka na każdym kroku sprawia, że odpowiedź jest jednoznaczna.

Spróbuj swoich sił

#include <stdlib.h>

int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
    // Napisz kod tutaj
    *returnSize = 0;
    return edges;
}