Bonjour, Une petite question : du coup forcément à la fin on refait toujours le chemin inverse pour vérifier qu'aucun sommet n'a été oublié ? donc on repasse forcément par la racine ? Merci, et vos vidéos sont d'utilité publique !!!
À la fin on est effectivement "de retour" sur le sommet de départ. Mais ce n'est pas vraiment pour vérifier qq chose que l'on revient en arrière. Le fait que l'on "retourne en arrière" est provoqué par la fin des appels récursifs. Pour mieux le comprendre qu'avec cette vidéo qui n'explore que les idées générales, il faudrait que vous lisiez l'algorithme tout en refaisant l'exemple que je donne.
Bon travail mais lorsqu'on me demande de répondre a ce question Parcourez en profondeur le graphe G en commençant le parcours à partir du noeud 1 est ce que je fais un graphique ou je cite le chemin que j'ai suivi en invoquant les noeuds aprez retour ?
À la découverte des graphes c’est ce qu’on me demande exactement de parcourir en profondeur le graphe G en commençant à partir di noeud 1 alors est ce que je fais le dessin de l’arbre connexe ? Ou bien je cite les sommets que j’ai suivi comme ça : 1-2-3-3-4-5-5-7-6 ?
Bonjour. Tant mieux si cette vidéo vous a aidé. Il ne faut pas la voir comme un cours mais comme une sorte de "tuto". Pour ce qui est des algorithmes je vous conseille le livre "Algorithmique", en français, édité chez Dunod, de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. C'est celui que je conseille pour avoir tous les détails. Ce livre est facile à trouver en librairie (on en trouve aussi d'occasion dans des éditions plus anciennes) ou dans une bibliothèque. Pour le parcours en largeur, vous trouverez sur ma chaine une vidéo un peu plus détaillée qui contient l'algorithme de manière plus explicite : "Retour sur le parcours en largeur".
Merci pour ces vidéos qui me sont très utiles pour m'initier à la théorie des graphes. Cependant j'ai une question : quand on parle d'un sommet (ou d'un noeud) couvert, signifie t'il que celui-ci est couvert par un arbre comme sur cette vidéo ? (la notion de noeud couvert est abordé dans des modèles de localisation discrets)
Bonjour. Sommet (ou noeud) couvert peut avoir plusieurs significations. Parfois je l'emploie de manière un peu informelle dans ces vidéos pour dire qu'un sommet fait partie d'un arbre en cours de construction (ou un couplage ou un autre objet en construction). Sinon, il y a d'autres sens plus précis qui semblent proches de ce que vous semblez chercher. + Allez voir mes vidéos sur les dominants par exemple ; on dit alors qu'un sommet est dominé (et non pas couvert (c'st le vocabulaire)) par un autre sommet (un voisin). + Vous pouvez aussi jeter un oeil sur ma vidéo sur le vertex-cover. Il s'agit de couvrir les ARETES d'un graphe par des sommets. Abonnez-vous à la chaine pour ne pas louper les nouvelles vidéos.
Il y a une autre vidéo plus approfondie sur le même algorithme sur ma chaine, si vous voulez aller plus dans les détails : ruclips.net/video/nfRsSozzAKY/видео.html
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
Incroyable , à la découverte de la chaîne qui va sauver mon ds
Il y a une autre vidéo plus approfondie sur le même sujet sur ma chaîne.
@@a_la_decouverte_des_graphes Super ! Je vais la regarder !
j'ai raté mon ds, pour l'examen je pense !
Très très bien expliqué merci beaucoup pour le travail monsieur
Magnifique tant de travail dans le montage vidéo je suis époustouflé
C’est très simple à faire en fait. J’ai fais une vidéo qui explique comment je fais si ça vous intéresse.
Merci pour votre explication courte et nette.❤
Très clair, limpide, concis!
Merçi beaucoup .. pour les explications.
très bien expliqué et les outils sont au top merci milles fois
Merci !
l’effet du feu est au top !
tu fais quoi comme études thamila ?
trés bonne vidéo j'ai compris en 15 min dés le premier visionnage
est ce qu il ya deferent resultat en graph parcoure en profandeur??
Bonjour,
Une petite question : du coup forcément à la fin on refait toujours le chemin inverse pour vérifier qu'aucun sommet n'a été oublié ? donc on repasse forcément par la racine ?
Merci, et vos vidéos sont d'utilité publique !!!
À la fin on est effectivement "de retour" sur le sommet de départ. Mais ce n'est pas vraiment pour vérifier qq chose que l'on revient en arrière. Le fait que l'on "retourne en arrière" est provoqué par la fin des appels récursifs. Pour mieux le comprendre qu'avec cette vidéo qui n'explore que les idées générales, il faudrait que vous lisiez l'algorithme tout en refaisant l'exemple que je donne.
Rien à redire! 👍
Avec quelle application avez vous conçu votre cours?, Camtasia?
Quel logiciel ou quel langage possédant quel module vous faites vos graphes ?
ruclips.net/video/kcAOPxIzIVU/видео.html
Merci monsieur
Bon travail mais lorsqu'on me demande de répondre a ce question
Parcourez en profondeur le graphe G en commençant le parcours à partir du noeud 1
est ce que je fais un graphique ou je cite le chemin que j'ai suivi en invoquant les noeuds aprez retour ?
Tout dépend de quoi vous avez besoin ou ce que l’on vous demande précisément. Au minimum il faut indiquer/décrire quel arbre a été construit.
À la découverte des graphes c’est ce qu’on me demande exactement de parcourir en profondeur le graphe G en commençant à partir di noeud 1 alors est ce que je fais le dessin de l’arbre connexe ? Ou bien je cite les sommets que j’ai suivi comme ça : 1-2-3-3-4-5-5-7-6 ?
est ce qu il ya deferent resultat en graph parcoure en profandeur??
Merci monsieur ❤
dr1 houbi
Merci énormément
Merci pour ce cour, il est très explicatif. Mais je voudrais savoir si l'on pourrais avoir ces différents algorithme écrit sous forme de programme.
Bonjour.
Tant mieux si cette vidéo vous a aidé. Il ne faut pas la voir comme un cours mais comme une sorte de "tuto".
Pour ce qui est des algorithmes je vous conseille le livre "Algorithmique", en français, édité chez Dunod, de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. C'est celui que je conseille pour avoir tous les détails. Ce livre est facile à trouver en librairie (on en trouve aussi d'occasion dans des éditions plus anciennes) ou dans une bibliothèque.
Pour le parcours en largeur, vous trouverez sur ma chaine une vidéo un peu plus détaillée qui contient l'algorithme de manière plus explicite : "Retour sur le parcours en largeur".
merci
Merci pour ces vidéos qui me sont très utiles pour m'initier à la théorie des graphes. Cependant j'ai une question : quand on parle d'un sommet (ou d'un noeud) couvert, signifie t'il que celui-ci est couvert par un arbre comme sur cette vidéo ? (la notion de noeud couvert est abordé dans des modèles de localisation discrets)
Bonjour.
Sommet (ou noeud) couvert peut avoir plusieurs significations. Parfois je l'emploie de manière un peu informelle dans ces vidéos pour dire qu'un sommet fait partie d'un arbre en cours de construction (ou un couplage ou un autre objet en construction).
Sinon, il y a d'autres sens plus précis qui semblent proches de ce que vous semblez chercher.
+ Allez voir mes vidéos sur les dominants par exemple ; on dit alors qu'un sommet est dominé (et non pas couvert (c'st le vocabulaire)) par un autre sommet (un voisin).
+ Vous pouvez aussi jeter un oeil sur ma vidéo sur le vertex-cover. Il s'agit de couvrir les ARETES d'un graphe par des sommets.
Abonnez-vous à la chaine pour ne pas louper les nouvelles vidéos.
À la découverte des graphes merci bcp c'est noté.
Cordialement
MERCI POUR LE TUTOT
Il y a une autre vidéo plus approfondie sur le même algorithme sur ma chaine, si vous voulez aller plus dans les détails :
ruclips.net/video/nfRsSozzAKY/видео.html
Voici l'implémentation en java de l'algo de BFS :
1ère classe(Arete) :
package demo;
public class Arrete {
@Override
public String toString() {
return "Arrete [sommet1=" + sommet1 + ", sommet2=" + sommet2 + ", poids=" + poids + "]";
}
String sommet1;
String sommet2;
int poids;
public String getSommet1() {
return sommet1;
}
public void setSommet1(String sommet1) {
this.sommet1 = sommet1;
}
public String getSommet2() {
return sommet2;
}
public void setSommet2(String sommet2) {
this.sommet2 = sommet2;
}
public int getPoids() {
return poids;
}
public void setPoids(int poids) {
this.poids = poids;
}
public Arrete(String sommet1, String sommet2, int poids) {
super();
this.sommet1 = sommet1;
this.sommet2 = sommet2;
this.poids = poids;
}
}
2ème :
package demo;
import java.util.ArrayList;
public class Graphe {
ArrayList arrete;
ArrayList sommets;
public void setSommets(ArrayList sommets) {
this.sommets = sommets;
}
public Graphe(ArrayList arrete, ArrayList sommets){
this.arrete = arrete;
this.sommets=sommets;
}
public void setArrete(ArrayList arrete) {
this.arrete = arrete;
}
public void addArrete(Arrete arrete) {
this.arrete.add(arrete);
}
public ArrayList getArrete() {
// TODO Auto-generated method stub
return arrete;
}
public ArrayList getSommets() {
// TODO Auto-generated method stub
return sommets;
}
public int poids(String sommet1,String sommet2) {
for (Arrete a :arrete) {
if (a.getSommet1().equals(sommet1)&&a.getSommet2().equals(sommet2)) {
return a.getPoids();
};
}
return 0;
}
}
package demo;
import java.util.ArrayList;
import java.util.Stack;
public class DFS {
public static void main(String[] args) {
Arrete D = new Arrete("A","E",10);
Arrete A = new Arrete("A","B",7);
Arrete B = new Arrete("B","C",1);
Arrete C = new Arrete("A","I",10);
//Arrete E = new Arrete("D","I",10);
ArrayList arrete = new ArrayList ();
arrete.add(A);
arrete.add(B);
arrete.add(C);
arrete.add(D);
//arrete.add(E);
ArrayList sommets = new ArrayList();
sommets.add("I");
sommets.add("E");
sommets.add("A");
sommets.add("B");
sommets.add("C");
sommets.add("D");
Graphe g = new Graphe(arrete,sommets);
///System.out.println(voisin("G ",g));
System.out.println("sommets visités à l'aide l'algo DFS : "+DFS(g,"A"));
System.out.println("sommets visités à l'aide l'algo BFS : "+BFS.BFS(g,"A"));
}
public static ArrayList DFS(Graphe G,String s) {
ArrayList arretes = G.getArrete();
ArrayList sommets = G.getSommets();
ArrayList sommetsVisites = new ArrayList();
Stack s1 = new Stack();
s1.push(s);
while(s1.size()!=0) {
String u = (String) s1.pop();
if(!sommetsVisites.contains(u)) {
sommetsVisites.add(u);
for(String j : BFS.voisin(u, G)) {
s1.push(j);
}
}
}
return sommetsVisites;
}
}
}
FIN
Je corrige il s'agit non pas du BFS mais du DFS !