Implementation (Part 1)
Lección 5 de 9 del curso Ordenamiento Topológico - Algoritmos de Grafos de Coddy.
Comenzamos con los grados de entrada, el corazón del algoritmo de Kahn.
Desafío
FácilEl motor del algoritmo de Kahn es el grado de entrada de cada vértice. Vamos a calcular eso primero.
Escribe una función llamada inDegrees que reciba n y el arreglo plano edges (pares dirigidos u -> v), y devuelva un arreglo donde la posición v sea el número de aristas que apuntan hacia el vértice v.
Por ejemplo, inDegrees(4, [0,1, 0,2, 1,3, 2,3]) devuelve [0, 1, 1, 2].
Pruébalo tú mismo
#include <stdlib.h>
int* inDegrees(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