Implementazione (Parte 2)

Lezione 6 di 9 del corso Ordinamento topologico - Algoritmi sui grafi di Coddy.

Ora rimuoviamo ripetutamente i vertici con grado entrante 0 per costruire l’ordinamento.

Sfida

Medio

Ora costruisci l'ordinamento completo.

Scrivi una funzione chiamata topologicalSort che riceva n e l'array piatto edges (archi diretti u -> v) e restituisca un ordinamento topologico dei vertici.

Usa l'algoritmo di Kahn: calcola i gradi entranti, poi prendi ripetutamente il vertice più piccolo con grado entrante 0, aggiungilo e riduci il grado entrante dei suoi vicini uscenti. Gli input di questa sfida sono aciclici.

Prendere il vertice più piccolo disponibile a ogni passaggio rende unica la risposta.

Provalo tu

#include <stdlib.h>

int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
    // Scrivi il codice qui
    *returnSize = 0;
    return edges;
}