Implementation (Part 2)
Lição 6 de 9 do curso Ordenação Topológica - Algoritmos de Grafos da Coddy.
Agora, removemos repetidamente os vértices de grau de entrada 0 para construir a ordem.
Desafio
MédioAgora construa a ordenação completa.
Escreva uma função chamada topologicalSort que recebe n e o array plano edges (direcionado u -> v), e retorna uma ordem topológica dos vértices.
Use o algoritmo de Kahn: calcule os graus de entrada (in-degrees), então repetidamente pegue o menor vértice com grau de entrada 0, adicione-o e reduza o grau de entrada de seus vizinhos de saída. As entradas para este desafio são acíclicas.
Pegar o menor vértice disponível a cada passo torna a resposta única.
Experimente você mesmo
#include <stdlib.h>
int* topologicalSort(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