Discussion :

[Aure7780]

Bonjour,

J'ai un algo que je n'arrive pas à convertir pour le faire en PHP.
J'essaye de faire du parcours en profondeur d'un graphe mais je n'y arrive pas !

Voici ce que j'ai déjà fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
function ParcoursProfondeur($graph, $sommet, $marquee = array())
{
	array_push($marquee, $sommet);
	echo $sommet;
	foreach($graph->getSommet($sommet)->getSuccesseur() as $succ) // pour chaque successeur de $sommet
	{
		if(!in_array($succ, $marquee)) // si il n'est pas marqué
		{
                        array_push($marquee, $succ); // on marque le sommet
			ParcoursProfondeur($graph, $succ, $marquee); // parcour en profondeur
		}
	}
}

le graphe que j'utilise est celui ci : Wiki
Sur le wiki on devrai obtenir : A, B, D, F, E, C, G
Moi j'obtiens : A, B, F, E, D, C, G, E, F

Algo itératif au cas où :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Initialement tous les sommets sont non marqués
La pile p est vide
Tant qu’il existe s non marquée, ouvrir s et l’insérer dans p
    Tant que p n’est pas vide
        S’il existe y non marquée voisin de x le sommet de p
        Alors ouvrir y et l’ins´erer dans p
        Sinon fermer x et supprimer x de p

Quelqu'un pourrait t-il me dire pourquoi ça ne fonctionne pas ?

[Petibidon]

Aie, je crois que je vais te donner une explication incompréhensible

Le problème que tu as, c'est que ta fonction récursive n'utilise pas un $marquee global.
Les modifications faites au passage sur B par exemple ne sont pas connues au niveau de A (ouais c'est vraiment pas clair...).

En gros, peut-être que cette modif dans la signature de la fonction devrait résoudre ton problème (pas certain sans tester)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

function ParcoursProfondeur($graph, $sommet, &$marquee )

Qui fera que tous les passages de la fonctions travailleront sur le même tableau.

Edit : Edit inutile -> viré

[Aure7780]

Merci c'était bien cela...

Je pensait qu'en passant une copie du tableau à chaque fois ça marcherait
mais il faut passer en référence... J'obtient maintenant : A,B,F,E,D,C,G
Il n'y a plus de doublon, donc ça me parait bien...