Prédecesseur d'un sommet
Fermé
noussa90
-
4 juin 2013 à 19:34
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 10 juin 2013 à 18:13
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 10 juin 2013 à 18:13
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
- Frédéric cherche à faire le buzz sur les réseaux sociaux. il a ajouté une image de manchots sur une image de plage. retrouvez l'image originale de la plage. que cachent les manchots ? - Forum Musique / Radio / Clip
- Taille 32x32 correspondance ✓ - Forum Loisirs / Divertissements
- Image iso - Guide
7 réponses
choubaka
Messages postés
39375
Date d'inscription
jeudi 4 avril 2002
Statut
Modérateur
Dernière intervention
14 avril 2024
2 100
5 juin 2013 à 12:28
5 juin 2013 à 12:28
Bonjour
Une question très nébuleuse, tu peux développer?
Une question très nébuleuse, tu peux développer?
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.
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
5 juin 2013 à 18:37
5 juin 2013 à 18:37
"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.
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
6 juin 2013 à 06:07
6 juin 2013 à 06:07
"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.
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
7 juin 2013 à 21:40
7 juin 2013 à 21:40
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
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
10 juin 2013 à 05:50
10 juin 2013 à 05:50
La matrice d'adjacence décrit la totalité du graphe, à partir de là on peut tout faire...
Avez-vous une idée comment procéder ?
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
10 juin 2013 à 06:00
10 juin 2013 à 06:00
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
L'algorithme de Dijkstra détermine le chemin le plus court et non le plus long.
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
10 juin 2013 à 18:13
10 juin 2013 à 18:13
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...
