1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| Sub listeCheminNoeud(ByVal noeudChemin As Integer, ByVal ordre As Single, ByRef matricegraph() As Single, ByRef listeInt As Collection, ByRef limite As Integer)
Dim noeud As Integer
Dim noeudOK() As Integer
Dim taille As Integer
Dim i As Integer
Dim cheminAnt As Integer
taille = -1
ReDim noeudOK(0)
'pb sur valeur de cheminant qui est consevé d'un appel recusrif à l'autre ... Cette variable doit conserver, au sein de l'appel le dernier chemin
'qui représente d'où on vient au sein de cet appel et dans tous les appels en cascade
'comme noeud ok par exemple qui représente la liste des noeuds accessibles et doit bien rester local au sein de chaque recursion
cheminAnt = (listeInt.Item(listeInt.Count))
'boucle qui cherche tous les noeuds adajcents dans la matrice
'et stock dans noeudOK()
'test si le nombre de nœuds parcouru est encre inférieur à la taille demandée
If limite > ordre Then
For noeud = 0 To UBound(matricegraph, 1)
If matricegraph(noeud, noeudChemin) = 1 Then
taille = taille + 1
ReDim Preserve noeudOK(taille)
noeudOK(taille) = noeud
End If
Next noeud
'si taille de noeudsOK() =0 alors pas de noeuds accessible adjacent = sortie d'appel récursif
'sinon pour chaque noeuds adjacents on fait la récursion:
If taille > -1 Then
For i = 0 To taille
'si le noeud adjacent est déja présent dans le parcours antérieur, alors on ne l'ajoute pas
'mais on le parcours quand même car il reste peut-être des chemins accesibles depuis celui-ci
'cette méthode provoquera des doublons mais assure le comptage des culs de sac et permet le rebours
'on incrément pas l'ordre
'testExist vérifie juste si le chiffre du noeuds est présent dans le nombre cheminAnt qui représente à chaque puissance de 10 l'ordre du chemin
If testExist(noeudOK(i) + 1, cheminAnt) Then
'on casse la connection = on est dejà passer par là
matricegraph(noeudOK(i), noeudChemin) = 0
Call listeCheminNoeud(noeudOK(i), ordre, matricegraph, listeInt, limite)
'on la remet = la matrice est en byref!
matricegraph(noeudOK(i), noeudChemin) = 1
Else
'si le noeud n'est pas présent, on l'ajoute, la puissance de 10 est incrémenté
matricegraph(noeudOK(i), noeudChemin) = 0
cheminAnt = cheminAnt + (noeudOK(i) + 1) * 10 ^ ordre
'imposible de modifier un élement de collection => remove et add
If listeInt.Count <> 0 Then
listeInt.Remove listeInt.Count
End If
listeInt.Add cheminAnt
'Debug.Print listeInt1(taillePrinc)
'ici on incrémente bien l'ordre
Call listeCheminNoeud(noeudOK(i), ordre + 1, matricegraph, listeInt, limite)
matricegraph(noeudOK(i), noeudChemin) = 1
End If
Next i
Else
'si il n'y a pas de noeuds accessible ici et que malgré tout l'ordre est toujours inférieur à l'ordre du chemin voulue,
'c'est un mauvais chemin, on l'efface et on remonte en recursion on reprenant le cheminAntérieur de la récursion parente
'sachant que le noeud où l'on est ici a bien ajouté avant et que l'on retire le chemin allé dans la matrice et pas le chemin retour
listeInt.Remove listeInt.Count
End If
End If
End Sub |
