Introduction

Bienvenue dans la suite de la série sur les Algorithmes de Graphes ! Cette fois, nous travaillons avec un graphe orienté, où chaque arête a une direction : une arête u -> v signifie que u doit venir avant v.

Le Tri Topologique organise les sommets d'un graphe orienté acyclique (DAG) en une ligne de sorte que chaque arête pointe vers l'avant. Il répond à des questions telles que « dans quel ordre puis-je suivre des cours compte tenu de leurs prérequis ? »

Le graphe est donné sous la forme de n (sommets 0 à n - 1) et edges, un tableau plat de paires orientées [u0, v0, u1, v1, ...] où chaque paire signifie u -> v.

Commençons !