Algorithme pour les composantes fortement connexes d'un graphe orienté.

[@alexandre-lu3jx]

Merci pour cette vidéo en particulier et pour la chaîne en général. Tout est très clairement expliqué!!

[@YuyeZhong-x1v]

Une excellente vidéo avec des explications graphiques parfaitement claires !

[@sawsenamz1918]

votre explication m'a sauvé ! merci infiniment

[@moa2487]

Pour ceux qui voudrait trouver plus d'exemples en ligne, le type de DFS fait pour la partie 1 de l'algorithme s'appelle un DFS post-ordre inverse !

[@RoroLeKing]

Merci pour cette vidéo, vous êtes super clair! merci!

[@a_la_decouverte_des_graphes]

Merci pour votre retour car j'ai un peu hésité à faire cette vidéo. Ce n'est pas simple de donner une vue d'ensemble de cette technique.

[@RoroLeKing]

​@@a_la_decouverte_des_graphes​ Je regarde vos vidéos en compléments de mes cours. Vous êtes à chaque fois plus clair et plus concis que ceux-ci. Merci pour votre travail.

[@a_la_decouverte_des_graphes]

Merci ! Du coup n'hésitez pas à partager avec vos collègue de promo., surtout en période de confinement...

[@gideol3646]

@@RoroLeKing Idem pour moi

[@anassimli]

Excellente vidéo merci ! Pouvez-vous corrigé un examen type des graphes ?

[@happylife9397]

Merci beaucoup monsieur. Moi j'utilise un autre algorithme : je marque + pour les successeurs et - pour les prédécesseur.

[@a_la_decouverte_des_graphes]

Et que faites-vous ensuite quand vous avez fait ces marques ?

[@happylife9397]

@@a_la_decouverte_des_graphes je prends par exemple le sommet "a", je marque "+" et "_" á ce sommet, après je marque "+" pour ces successeurs (même pour les successeurs des successeurs) , après on revient à "a" et on marque "_" pour tous les prédécesseurs (et prédécesseur s des prédécesseurs)mais seulement pour les sommets qui ont déjà un "+" , après l'ensemble des sommets ayant "+" et "_" constituent la composante fortement connexe contenant le sommet a . Je sais pas si c'est bien expliquer.

[@ruhtra4267]

@@happylife9397 Le problème de cet algorithme, c'est que si tu veux trouver toutes les composantes fortement connexes, il n'est pas linéaire non ?

[@douarmedouailislam1840]

c'est quoi le nom de cet algorithme s'il te plait ? je le cherche mais je n'ai pas le nom

[@mohamedelmatal6820]

où puis je trouver la preuve de l'algorithme de kosaraju ? 🥰

[@laurent__9032]

Merci beaucoup pour cette explication limpide. Ayant du mal à bien comprendre Tarjan pensez vous un jour faire une vidéo dessus ? Merci

[@ruhtra4267]

C'est bien Kosaraju qui est expliqué dans le Cormen, même s'il n'est pas nommé comme ça. Je préfère Kosaraju à Tarjan, même si j'ai entendu dire que la méthode en contractant les cycles avec Union-Find (bien que légèrement plus lente), soit plus claire. Vos vidéos sont de grande qualité. Comptez-vous rester sur la théorie des graphes, ou allez-vous élargir à l'algorithmique en général ? Par ailleurs, dans le Cormen, je trouve que certaines choses manquent, comme la décomposition lourd-léger ou la décomposition par centroïdes par exemple, qui sont pourtant cruciales sur les arbres.

[@a_la_decouverte_des_graphes]

Merci pour vos précisions. Le Cormen est un livre généraliste sur l'algorithmique, qui ne traite pas que des graphes. Mais comme : il est facile à trouver et qu'il traite aussi des structures de données, je pense que c'est une bonne référence, au moins pour une première approche. A priori je ne pense pas sortir du domaine des graphes sur cette chaine. Mais, qui sait, peut-être un jour une chaine secondaire pour parler d'autres sujets...

[@ilouse1]

bonjour dans la partie 1, quand on veut choirisir le sommet de depart à chaque DFS, est ce que le choix est arbitraire ?

[@federicocastro5542]

Si seulement mon professeur de ma fac expliquerait comme vous le faîtes ...

[@najdk1930]

Bonjour, est-ce que pour trouver cette fameuse liste sans l'inverser on peut directement appliquer l'ordre topologique? Merci à vous :)

[@pierretourneur-silvain6245]

Bonjour, pourriez vous faire une vidéo concernant l'algorithme de Warshall pour trouver les composantes fortement connexes maximales ? Merci pour votre travail.

[@younesaitmha]

merci beaucoup vous vulgarisait très bien les concepts. j'ai juste une demande est ce qu'on peut voire des démonstrations et de la théorie dans vous cours ?

[@a_la_decouverte_des_graphes]

Dans certains de mes cours oui je donne des preuves dans d’autres je donne parfois des « idées des preuves » tout dépend du public, du niveau, des attentes. Dans mon livre je fais un peu des deux...

[@younesaitmha]

@@a_la_decouverte_des_graphes si j'ai compris vous faites pas de théorie parce qu'il n'est pas à la porté de tout le public une chose qu'est vraie.

[@yak_music]

On dirait un tri topologique pour la partie 1. 😊

[@sinemarik5476]

je t'aime

[@a_la_decouverte_des_graphes]

Moi non plus

[@mrreese2342]

est ce que c'est l'arlgorithme de malgrange ?

[@laibayoub9854]

Ja crois algorithme de marquage

[@Amel-cc9lu]

s'agit-il de l'algorithme de Tarjan ?

[@musiclyrics9562]

c'est l'algorithme de kasaraju

[@musiclyrics9562]

*kosaraju

[@thefantasicm_2407]

je trouve que le fonctionnement de l'algorithme de Kosaraju est moins clair que celui de Tarjan, il faut réfléchir un peu plus pour comprendre sa validité.

[@a_la_decouverte_des_graphes]

Peut-être mais ça dépend aussi de la compréhension fine que l'on a du DFS. Notez que l'objectif de ma vidéo n'est pas de présenter la preuve de validité mais, beaucoup plus modestement, d'en donner un aperçu sur un petit exemple.

[@thefantasicm_2407]

@@a_la_decouverte_des_graphes bien sur, bonne vidéo au passage !

[@a_la_decouverte_des_graphes]

@@thefantasicm_2407 J'ai un peu hésité à faire une vidéo sur ce sujet car ça ne me paraissait pas simple à présenter, à vulgariser. Mais comme c'est un thème "classique" je me suis lancé (bien aidé par le COVID-19 qui me force à rester chez moi...).