Implementation (Part 1)
Lição 5 de 9 do curso Ordenação Topológica - Algoritmos de Grafos da Coddy.
Começamos com os graus de entrada, o coração do algoritmo de Kahn.
Desafio
FácilO motor do algoritmo de Kahn é o grau de entrada (in-degree) de cada vértice. Vamos calcular isso primeiro.
Escreva uma função chamada inDegrees que receba n e o array unidimensional edges (pares direcionados u -> v), e retorne um array onde a posição v é o número de arestas que apontam para o vértice v.
Por exemplo, inDegrees(4, [0,1, 0,2, 1,3, 2,3]) retorna [0, 1, 1, 2].
Experimente você mesmo
#include <stdlib.h>
int* inDegrees(int n, int* edges, int edges_size, int* returnSize) {
// Escreva o código aqui
*returnSize = 0;
return edges;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Ordenação Topológica - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity