Scribd
Importer
16 vues2 pages

Algorithme des Composantes Connexes

L'algorithme ComposanteFortementConnexe permet d'identifier un sous-ensemble de sommets d'un graphe à partir d'un sommet donné. L'algorithme ComposantesFortementConnexes utilise cette fonction pour déterminer toutes les composantes fortement connexes d'un graphe. Les deux algorithmes fonctionnent en explorant les sommets et en marquant ceux qui ont été examinés.

Transféré par

Salma Hadded
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
16 vues2 pages

Algorithme des Composantes Connexes

L'algorithme ComposanteFortementConnexe permet d'identifier un sous-ensemble de sommets d'un graphe à partir d'un sommet donné. L'algorithme ComposantesFortementConnexes utilise cette fonction pour déterminer toutes les composantes fortement connexes d'un graphe. Les deux algorithmes fonctionnent en explorant les sommets et en marquant ceux qui ont été examinés.

Transféré par

Salma Hadded
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Algorithme : ComposanteFortementConnexe

Entrées: G = (X;U) un graphe, a un sommet


Sortie: X un sous-ensemble de sommets

Début
X1 ← {a};
pour tout x X faire examiné(x) ← faux;
tant que x X1 / non examiné(x) faire
examiné(x) ← vrai;
pour tout u = (x;y) U / y X1 faire
X1 ← X1 {y};
fin tant que;
X2 ← {a};
pour tout x X1 faire examiné(x) ← faux;
tant que x X2 / non examiné(x) faire
examiné(x) ← vrai;
Anissa OMRANE pour tout Cheminement
(FST 2025-2026) u = (y;x) Udans/ lesyGraphes
et Connexité X2 faire 36 / 42
Algorithme : ComposantesFortementConnexes

Entrées: G = (X;U) un graphe


Sortie: C = {C,...,C} ensemble de composantes

Début
X’ ← X;
i ← 1;
tant que X’ faire
choisir x dans X’;
C ← ComposanteFortementConnexe(G,x);
X’ ← X’ - C;
i ← i + 1;
fin tant que;
Fin

Anissa OMRANE (FST 2025-2026) Cheminement et Connexité dans les Graphes 37 / 42

Vous aimerez peut-être aussi