Comment trasnformer une matrice à un arbre ? [Résolu]

Messages postés
291
Date d'inscription
dimanche 4 octobre 2009
Statut
Membre
Dernière intervention
25 août 2014
- - Dernière réponse : begueradj
Messages postés
291
Date d'inscription
dimanche 4 octobre 2009
Statut
Membre
Dernière intervention
25 août 2014
- 6 déc. 2011 à 00:49
Bonjour

Je cherche à transformer une matrice qui ne contient que des 0 et des 1 à un arbre. Comment le faire sachant que je ne m'intéresse à ne représenter sous forme d'un arbre que les Matrice[i][j] =0 ?
Afficher la suite 

8 réponses

Meilleure réponse
Messages postés
12336
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
27
3
Merci
ok bon... déjà, tu remplaces si matrice[i][j] par si non matrice[i][j] pour transformer ta matrice en un graph.

Bon sinon, c'est un exemple super simple de parcours de graphs...

voici un dfs, ça ne te renvoie pas le chemin le plus court, mais ça marche sans transformer ta matrice en graph.

int solution(int **m, int n, int d, int e){
if (d == e) return 1;
int i;
for (i = 0; i < n; i++){
if (!m[d][i]){
m[d][i] = 1;
if (solution(m, n, i, e)) return 1;
}
}
return 0;
}

d c'est le noeud de départ
e c'est le noeud d'arrivée
ma fonction renvoie 1 si il y a un chemin, mais stoquer le chemin c'est pas vraiment difficile.

Je t'ai donné le dfs, tu peux chercher toi même comment on fait un bfs, et NON, t'as pas besoin d'une pile, juste d'allouer deux tableaux de taille n.

Bref, le BFS c'est super simple à faire, j'ai vu des jeunes de 14 ans le faire pour le concours prologin...

Fait au moins preuve de courage et commence à faire ton travail tout seul, on t'aidera à débuguer le truc si besoin, mais on ne le fera pas "entièrement" à ta place.

Cordialement,

Maxime

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 196 internautes nous ont dit merci ce mois-ci

Commenter la réponse de coucou747
Messages postés
291
Date d'inscription
dimanche 4 octobre 2009
Statut
Membre
Dernière intervention
25 août 2014
1
0
Merci
Précision:
Sachant que pour la configuration, on a toujours une case de départ et une case d'arrivée et, je répète, je ne m'intéresse qu'aux 0
Commenter la réponse de begueradj
Messages postés
14636
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
9 octobre 2019
90
0
Merci
Hello,
Quel forme d'arbre? Quel est l'objectif final?


@+
Buno, Admin CS
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
Commenter la réponse de BunoCS
Messages postés
291
Date d'inscription
dimanche 4 octobre 2009
Statut
Membre
Dernière intervention
25 août 2014
1
0
Merci
Merci de m'avoir répondu.

EN fait, dans ma matrice, je n'ai que des 0 et des 1.

Je prédéfinis ma case de départ et ma case d'arrivée, qui ont comme contenu 0 (je ne m'intéresse qu'aux 0)

Dans cette matrice, je cherche le chemin de la case de départ à la case d'arrivée en enmpruntant que les 0.

On nous a demandé d'implémenter l'algorithme du meilleur d'abord. Or, l'implémenter directement sur la matrice est difficile, donc si je réussis à transformer la matrice à un arbre où les successeurs de la case de départ valant 0 et menant ou pas à la case finale, je pourrais parcourir mon arbre plus facilement.
Commenter la réponse de begueradj
Messages postés
14636
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
9 octobre 2019
90
0
Merci
Tu peux définir les fils de tes noeuds comme les voisins de la case courante de la matrice par exemple.


@+
Buno, Admin CS
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
Commenter la réponse de BunoCS
Messages postés
12336
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
27
0
Merci
Salut,

Une matrice représente un graph et non un arbre.

Il suffit de commencer par allouer N noeuds dans un tableau, puis de se déplacer dans ta matrice pour ajouter les arrètes.

en gros
allouer un tableau de N noeuds
pour i de 0 à N
pour j de 0 à N
si matrice[i][j]
ajouter une arrète de i à j

c'est super simple.

Cordialement.
Commenter la réponse de coucou747
Messages postés
291
Date d'inscription
dimanche 4 octobre 2009
Statut
Membre
Dernière intervention
25 août 2014
1
0
Merci
merci pour vos réponses

mais le fait d'arrivé à un élément 0 ne contenant pas de successeurs, je dois remonter en arrière, pour retrouver ma bifurcation et aller dans l'autre côté. Ce retour en arrière, je pense qu'il nécessite une pile, et ça me pose un problème.
Commenter la réponse de begueradj
Messages postés
291
Date d'inscription
dimanche 4 octobre 2009
Statut
Membre
Dernière intervention
25 août 2014
1
0
Merci
Merci pour vos éclaircissements et vos encouragement, Maxime.
Commenter la réponse de begueradj