L'algorithme de Kahn, utilisé pour le tri topologique dans un graphe orienté, détecte la présence d'un cycle orienté de la manière suivante :

Principe de détection du cycle

Calcul des degrés entrants :

Pour chaque sommet du graphe, on calcule son degré entrant (nombre d'arcs arrivant vers ce sommet).

Initialisation de la file :

On place dans une file (FIFO ordinaire ; une file de priorité sert seulement si l'on veut un ordre topologique lexicographique) tous les sommets dont le degré entrant est égal à 0 (sommets sans dépendance).

Traitement itératif :

On retire un sommet de la file, on le place dans l'ordre topologique, et on décrémente le degré entrant de ses voisins (sommets vers lesquels il pointe).
Si un voisin voit son degré entrant atteindre 0, on l'ajoute à la file.

Détection du cycle :

Si, à la fin de l'algorithme, tous les sommets ont été traités (
ordre
=
𝑉
ordre=V), le graphe est sans cycle (DAG, Directed Acyclic Graph).
Si au moins un sommet n'a pas été traité, cela signifie qu'il existe un cycle orienté dans le graphe : le sous-graphe induit par les sommets restants contient au moins un cycle (chaque sommet restant a encore un degré entrant 
≥
1
≥1 dans ce sous-graphe, ce qui force l'existence d'un circuit). Attention : un sommet restant n'appartient pas nécessairement à un cycle, il peut simplement être atteignable depuis un cycle (ex. 
𝐴
→
𝐵
→
𝐴
A→B→A et 
𝐴
→
𝐶
A→C : 
𝐶
C n'est jamais traité sans être dans le cycle).

Exemple
Graphe avec un cycle 
𝐴
→
𝐵
→
𝐶
→
𝐴
A→B→C→A :
Degrés entrants initiaux : 
𝐴
:
1
A:1, 
𝐵
:
1
B:1, 
𝐶
:
1
C:1.
Aucun sommet n'a un degré entrant de 0 : la file est vide dès le début.
Aucun sommet n'est traité (
0
≠
3
0

=3) 
⇒
⇒ cycle détecté.

Pourquoi ça marche ?
Dans un graphe sans cycle fini non vide, il existe toujours au moins un sommet de degré entrant nul, et cette propriété est préservée après suppression d'un tel sommet : tous les sommets sont donc traités.
Dans un graphe fini non vide où tout sommet a un degré entrant 
≥
1
≥1, en remontant les arcs on repasse forcément par un sommet déjà visité : il y a un cycle. C'est exactement la situation du sous-graphe résiduel.

Complexité
Temps : 
𝑂
(
𝑉
+
𝐸
)
O(V+E) (où 
𝑉
V est le nombre de sommets et 
𝐸
E le nombre d'arcs).
Espace : 
𝑂
(
𝑉
)
O(V) (degrés entrants + file).

Code Python (illustration)
from collections import deque

def kahn(graphe):
graphe est un dictionnaire {sommet: [voisins]}
degre_entrant = {u: 0 for u in graphe}
for u in graphe:
for v in graphe[u]:
degre_entrant[v] += 1

file = deque([u for u in degre_entrant if degre_entrant[u] == 0])
ordre_topologique = []

while file:
u = file.popleft()
ordre_topologique.append(u)
for v in graphe[u]:
degre_entrant[v] -= 1
if degre_entrant[v] == 0:
file.append(v)

if len(ordre_topologique) != len(graphe):
return "Cycle détecté !"
else:
return "Pas de cycle. Ordre topologique : " + str(ordre_topologique)

Cas particuliers
Graphe vide : pas de cycle.
Sommets isolés : traités immédiatement, pas de cycle.
Boucle sur un sommet (
𝑢
→
𝑢
u→u) : degré entrant jamais nul, détectée comme cycle.
Graphe fortement connexe à 
≥
2
≥2 sommets : tous les degrés entrants sont 
≥
1
≥1, donc cycle.

Limites
Kahn détecte le cycle mais ne l'exhibe pas : les sommets non traités forment seulement un sur-ensemble des sommets des cycles. Pour extraire les cycles eux-mêmes, on utilise un DFS avec coloration (arc arrière) ou Tarjan / Kosaraju (composantes fortement connexes).