Algorithme pour les composantes fortement connexes d'un graphe orienté.
Vložit
- čas přidán 15. 04. 2020
- Description (ni formelle ni complète) sur un exemple d'un algorithme permettant de trouver les composantes fortement connexes d'un graphe orienté.
Je vous invite à regarder la vidéo "Partie 1" qui décrit le problème et, éventuellement, revoir l'algorithme du parcours en profondeur (DFS) qui est utilisé ici comme outil. - Věda a technologie
Merci pour cette vidéo en particulier et pour la chaîne en général. Tout est très clairement expliqué!!
Une excellente vidéo avec des explications graphiques parfaitement claires !
votre explication m'a sauvé ! merci infiniment
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 !
Si seulement mon professeur de ma fac expliquerait comme vous le faîtes ...
Merci beaucoup pour cette explication limpide. Ayant du mal à bien comprendre Tarjan pensez vous un jour faire une vidéo dessus ? Merci
Merci pour cette vidéo, vous êtes super clair! merci!
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.
@@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.
Merci !
Du coup n'hésitez pas à partager avec vos collègue de promo., surtout en période de confinement...
@@RoroLeKing Idem pour moi
Excellente vidéo merci ! Pouvez-vous corrigé un examen type des graphes ?
Bonjour, pourriez vous faire une vidéo concernant l'algorithme de Warshall pour trouver les composantes fortement connexes maximales ? Merci pour votre travail.
Merci beaucoup monsieur.
Moi j'utilise un autre algorithme : je marque + pour les successeurs et - pour les prédécesseur.
Et que faites-vous ensuite quand vous avez fait ces marques ?
@@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.
@@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 ?
c'est quoi le nom de cet algorithme s'il te plait ? je le cherche mais je n'ai pas le nom
Bonjour, est-ce que pour trouver cette fameuse liste sans l'inverser on peut directement appliquer l'ordre topologique? Merci à vous :)
bonjour
dans la partie 1, quand on veut choirisir le sommet de depart à chaque DFS, est ce que le choix est arbitraire ?
où puis je trouver la preuve de l'algorithme de kosaraju ? 🥰
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.
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...
On dirait un tri topologique pour la partie 1. 😊
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 ?
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...
@@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.
est ce que c'est l'arlgorithme de malgrange ?
Ja crois algorithme de marquage
je t'aime
Moi non plus
s'agit-il de l'algorithme de Tarjan ?
c'est l'algorithme de kasaraju
*kosaraju
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é.
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.
@@a_la_decouverte_des_graphes bien sur, bonne vidéo au passage !
@@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...).