A voir également:
- Dans la présentation à télécharger, déplacez l'image dans le cadre sans en modifier la taille. redressez l'image pour que le niveau de la mer soit à l'horizontale. faites correspondre : la ligne avec le niveau de la mer ; le point avec le sommet de la grande voile. combien d'oiseaux sont dans le cadre ?
- Comment réduire la taille d'un fichier - Guide
- Aller à la ligne excel - Guide
- Partage de photos en ligne - Guide
- Reduire taille image - Guide
- Appliquez à tous les paragraphes du document à télécharger, à l’exception des titres et des sous-titres, la mise en forme suivante : chaque paragraphe doit être espacé de 0,42 cm ou 12 pt du paragraphe qui suit les textes ne doivent pas être en retrait à droite et à gauche après ces modifications, sur quelle page se trouve le titre « la cheminée » dans le chapitre « informations diverses » ? - Guide
7 réponses
Bonjour ,
En fait, je veux déterminer le niveau d'un sommet c'est à dire sa profondeur dans le graphe. J'ai pu y arriver par écrire un algorithme qui détermine les prédécesseurs de chaque sommet et par la suite attribuer le niveau i au sommet qui n'a pas de prédécesseurs ( commençons par la racine). Une fois c'est fait , je vais enlever ce sommet, s'il existe dans les prédécesseurs de tout le reste des sommets ( à qui on n'a pas encore attribuer de niveau ) et boucler jusqu'à finir avec tous les sommets. Je classe au fur et à mesure les niveaux dans un tableau et après j'accède au niveau souhaité avec l'indice du sommet entré en paramètre.
En fait, je veux déterminer le niveau d'un sommet c'est à dire sa profondeur dans le graphe. J'ai pu y arriver par écrire un algorithme qui détermine les prédécesseurs de chaque sommet et par la suite attribuer le niveau i au sommet qui n'a pas de prédécesseurs ( commençons par la racine). Une fois c'est fait , je vais enlever ce sommet, s'il existe dans les prédécesseurs de tout le reste des sommets ( à qui on n'a pas encore attribuer de niveau ) et boucler jusqu'à finir avec tous les sommets. Je classe au fur et à mesure les niveaux dans un tableau et après j'accède au niveau souhaité avec l'indice du sommet entré en paramètre.
"sa profondeur dans le graphe."
C'est quoi la profondeur d'un noeud ?
"détermine les prédécesseurs de chaque sommet"
Ca va dépendre de ta structure de graphe, le plus simple est de faire un chaînage arrière comme pour une liste chaînée : lorsque tu fais un arc, le noeud cible est informé de son prédecesseur.
"commençons par la racine"
Sauf cas particulier (arbres nottament) un graphe n'a pas de "racine", tu ne peux donc pas commencer...
"le niveau i au sommet qui n'a pas de prédécesseurs"
C'est quoi i ?
"s'il existe dans les prédécesseurs de tout le reste des sommets ( à qui on n'a pas encore attribuer de niveau )"
Tu ne vas pas enlever grand chose alors...
"finir avec tous les sommets"
Es tu sûr que ton algorithme se termine vraiment ? J'ai des doutes...
"Je classe au fur et à mesure les niveaux dans un tableau"
A priori dans un graphe tu devrais avoir des sommets qui ont le même niveau, ce seul critère ne suffit pas à faire un classement.
"j'accède au niveau souhaité avec l'indice du sommet"
Du coup, ça sert à quoi le classement ?
C'est pas très au point tout ça... commence déjà par formaliser ton algorithme, des phrases approximatives ne permettent pas de décrire ton raisonnement, qui est lui aussi à revoir.
C'est quoi la profondeur d'un noeud ?
"détermine les prédécesseurs de chaque sommet"
Ca va dépendre de ta structure de graphe, le plus simple est de faire un chaînage arrière comme pour une liste chaînée : lorsque tu fais un arc, le noeud cible est informé de son prédecesseur.
"commençons par la racine"
Sauf cas particulier (arbres nottament) un graphe n'a pas de "racine", tu ne peux donc pas commencer...
"le niveau i au sommet qui n'a pas de prédécesseurs"
C'est quoi i ?
"s'il existe dans les prédécesseurs de tout le reste des sommets ( à qui on n'a pas encore attribuer de niveau )"
Tu ne vas pas enlever grand chose alors...
"finir avec tous les sommets"
Es tu sûr que ton algorithme se termine vraiment ? J'ai des doutes...
"Je classe au fur et à mesure les niveaux dans un tableau"
A priori dans un graphe tu devrais avoir des sommets qui ont le même niveau, ce seul critère ne suffit pas à faire un classement.
"j'accède au niveau souhaité avec l'indice du sommet"
Du coup, ça sert à quoi le classement ?
C'est pas très au point tout ça... commence déjà par formaliser ton algorithme, des phrases approximatives ne permettent pas de décrire ton raisonnement, qui est lui aussi à revoir.
Bonsoir ,
Par profondeur d'un noeud, je veux dire son niveau dans le graphe.
En fait, mon graphe est construit à partir d'une matrice d'adjacence et non pas d'une liste.
Je travaille sur les ontologies et donc mon graphe ce n'est qu'une représentation symbolique pour pouvoir manipuler mes concepts et faire les tests (bien évidemment je suis dans le cas particulier des arbres).
Par « i » je désigne le numéro du niveau du noeud dans le graphe.
L'algorithme je l'ai exécuté à la main et il marche super bien mais je bloque dans l'implémentation des prédécesseurs d'un noeud.
Par profondeur d'un noeud, je veux dire son niveau dans le graphe.
En fait, mon graphe est construit à partir d'une matrice d'adjacence et non pas d'une liste.
Je travaille sur les ontologies et donc mon graphe ce n'est qu'une représentation symbolique pour pouvoir manipuler mes concepts et faire les tests (bien évidemment je suis dans le cas particulier des arbres).
Par « i » je désigne le numéro du niveau du noeud dans le graphe.
L'algorithme je l'ai exécuté à la main et il marche super bien mais je bloque dans l'implémentation des prédécesseurs d'un noeud.
"bien évidemment je suis dans le cas particulier des arbres"
C'était loin d'être évident, vu toutes les sortes de graphe qu'il existe !
"mon graphe est construit à partir d'une matrice d'adjacence"
"je bloque dans l'implémentation des prédécesseurs d'un noeud"
Dans ta matrice d'adjacence tu as une case au "croisement" de chaque couple de noeuds source/cible relié par un arc, la lecture d'un prédécesseur est donc immédiat, il suffit de lire pour le noeud concerné toute la ligne (ou la colonne) et trouver les arcs dont il est cible.
Remarque : dans le cas d'un arbre, la matrice d'adjacence va être creuse, c'est à mon avis une mauvaise idée de représentation...
C'était loin d'être évident, vu toutes les sortes de graphe qu'il existe !
"mon graphe est construit à partir d'une matrice d'adjacence"
"je bloque dans l'implémentation des prédécesseurs d'un noeud"
Dans ta matrice d'adjacence tu as une case au "croisement" de chaque couple de noeuds source/cible relié par un arc, la lecture d'un prédécesseur est donc immédiat, il suffit de lire pour le noeud concerné toute la ligne (ou la colonne) et trouver les arcs dont il est cible.
Remarque : dans le cas d'un arbre, la matrice d'adjacence va être creuse, c'est à mon avis une mauvaise idée de représentation...
Bonsoir ,
Avec la matrice d'adjacence, je peux lire directement les successeurs de mon noeud source et non les prédécesseurs.
Avec la matrice d'adjacence, je peux lire directement les successeurs de mon noeud source et non les prédécesseurs.
Voici un arbre :
Et voici la matrice d'adjacence associée :
En ligne, tu lis les successeurs, par exemple, ligne B, les successeurs sont A et C.
En colonne, tu lis les prédécesseurs, par exemple, colonne B, le prédécesseur c'est D.
Il est donc tout à fait possible de lire directement les prédécesseurs dans la matrice d'adjacence.
D / \ B E / \ A C
Et voici la matrice d'adjacence associée :
A B C D E A 0 0 0 0 0 B 1 0 1 0 0 C 0 0 0 0 0 D 0 1 0 0 1 E 0 0 0 0 0
En ligne, tu lis les successeurs, par exemple, ligne B, les successeurs sont A et C.
En colonne, tu lis les prédécesseurs, par exemple, colonne B, le prédécesseur c'est D.
Il est donc tout à fait possible de lire directement les prédécesseurs dans la matrice d'adjacence.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Bonsoir ,
A partir de la matrice d'adjacence, peut-on déterminer le chemin le plus long qui mène à un sommet X.
Merci à vous
A partir de la matrice d'adjacence, peut-on déterminer le chemin le plus long qui mène à un sommet X.
Merci à vous
alexdu17200 a déjà répondu à ta question !
https://forums.commentcamarche.net/forum/affich-27950985-chemin-le-plus-long
https://forums.commentcamarche.net/forum/affich-27950985-chemin-le-plus-long
Toute la force d'un algorithme comme celui de Dijkstra est de pouvoir être utilisé dans bien d'autres domaines que celui auquel il était destiné au départ. Une fois que tu auras mis en place l'algorithme de Dijkstra pour le plus court chemin il y aura peu de choses à modifier pour trouver le plus long chemin.
Cependant, je trouve à titre personnel que ce serait une énorme perte de temps, parce que tu travailles sur des arbres qui ont pour propriété de n'avoir qu'un seul chemin entre deux noeuds, Si tu trouves un chemin entre deux noeuds sur un arbre tu auras trouvé le plus court et le plus long...
Cependant, je trouve à titre personnel que ce serait une énorme perte de temps, parce que tu travailles sur des arbres qui ont pour propriété de n'avoir qu'un seul chemin entre deux noeuds, Si tu trouves un chemin entre deux noeuds sur un arbre tu auras trouvé le plus court et le plus long...