Implementation (Part 2)
Lección 6 de 9 del curso Ordenamiento Topológico - Algoritmos de Grafos de Coddy.
Ahora eliminamos repetidamente los vértices con grado de entrada 0 para construir el orden.
Desafío
IntermedioAhora construye el ordenamiento completo.
Escribe una función llamada topologicalSort que reciba n y el arreglo plano edges (dirigido u -> v), y devuelva un orden topológico de los vértices.
Usa el algoritmo de Kahn: calcula los grados de entrada (in-degrees), luego toma repetidamente el vértice más pequeño con grado de entrada 0, añádelo y reduce el grado de entrada de sus vecinos de salida. Las entradas para este desafío son acíclicas.
Tomar el vértice más pequeño disponible en cada paso hace que la respuesta sea única.
Pruébalo tú mismo
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// Escribe el código aquí
*returnSize = 0;
return edges;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Ordenamiento Topológico - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity