Implementation (Part 1)

Leçon 5 sur 9 du cours Tri topologique - Algorithmes de graphes de Coddy.

Nous commençons par les degrés entrants, le cœur de l'algorithme de Kahn.

Défi

Facile

Le moteur de l'algorithme de Kahn est le degré entrant (in-degree) de chaque sommet. Commençons par calculer cela.

Écrivez une fonction nommée inDegrees qui prend n et le tableau plat edges (paires orientées u -> v), et renvoie un tableau où la position v est le nombre d'arêtes pointant vers le sommet v.

Par exemple, inDegrees(4, [0,1, 0,2, 1,3, 2,3]) renvoie [0, 1, 1, 2].

Essayez vous-même

#include <stdlib.h>

int* inDegrees(int n, int* edges, int edges_size, int* returnSize) {
    // Écrire le code ici
    *returnSize = 0;
    return edges;
}

Testez-vous

Cette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.

Toutes les leçons de Tri topologique - Algorithmes de graphes

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2