cs_liegeus
Messages postés2Date d'inscriptionlundi 25 octobre 2004StatutMembreDernière intervention25 mai 2007
-
17 mai 2007 à 00:09
Julien237
Messages postés883Date d'inscriptionvendredi 3 novembre 2000StatutMembreDernière intervention 3 mars 2009
-
17 mai 2007 à 10:04
Bonjour, voilà j'essai de faire un programme simple qui parcours un graphe (défini en dur dans le code)
j'utilise une collection (appellé "marque")dans laquelle je rajoute les sommets que je parcours (marque.add) afin de savoir si je suis déjà passé dessus précédemment sauf que après quand je veux vérifier si le sommet est déjà présent avec un marque.Contains(c) = False (c étant la variable integer comprenant le numero de mon sommet)
ben il ne trouve jamais le sommet dans la collection alors que il rajoute bel et bien des choses dedans... je pense que ça doit etre un problème de type mais je comprend pas vraiment là...
lerci beaucoup de prendre le temps de regarder...
je vous met mon code :
<hr size="2" width="100%" />
Public Class Form1
Dim adj(9, 9) As Object 'définition de la matrice d'adjacence
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
Dim successeurs As New Collection 'Contient les successeurs d'un noeud du graphe
Dim noeuds As New Collection 'contient tous les noeuds du graphe
Dim k As Integer
Dim i As Integer
For k = 1 To 9 'remplir les noeuds (de 1 à 9)
noeuds.Add(Item:=k)
Next k
For Each k In noeuds 'calcul des successeurs d'un noeud
For i = 1 To 9
If adj(i, k) = 1 Then
successeurs.Add(Item:=k)
End If
Next i
Next k
MsgBox("matrice initialisé")
End Sub
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim pile As New Stack 'va servir de pile
Dim marque As New Collection 'sert à marquer les noeuds déjà parcourus
Dim start As Integer
Dim c As Integer
Label3.Visible = True
TextBox1.Visible = True
start = CInt(ListBox1.Text)
marque.Add(start) 'on marque le premier sommet selectionné
pile.Push(start) 'on empile le sommet que l'on vient de marquer
TextBox1.Text = start 'on affiche le noeud que l'on vient de parcourir
MsgBox("nombre de choses la collection dans marque : " & marque.Count)
While pile.Count <> 0 'tant que la pile n'est pas vide
MsgBox("nombre de donné dans la pile :" & pile.Count)
For c = 1 To 9 If adj(start, c) 1 And marque.Contains(c) False
Then 'si le sommet adj (i,j) est un successeur non marqué
marque.Add(c) 'ont le marque
pile.Push(c) 'on l'empile
MsgBox("on vient d'empiler et marquer :" & c)
MsgBox("nombre de choses la collection dans marque : " & marque.Count)
TextBox1.Text = TextBox1.Text & "," & c 'on l'affiche à la suite des autres sommets dejà parcourus
End If
Next
c = pile.Pop() 'on prend le dernier sommet de la pile
MsgBox("le dernier sommet de la pile est :" & c)
MsgBox("lavaleur de start est :" & start)
start = c 'on reboucle à partir du somment que l'on vient de dépiler
MsgBox("la valeur de start est maintenant de" & start)
MsgBox("nombre de donné dans la pile :" & pile.Count)
'pile.Pop()
MsgBox("nombre de donné dans la pile :" & pile.Count)
MsgBox("le dernier sommet de la pile est :" & c)
End While
Julien237
Messages postés883Date d'inscriptionvendredi 3 novembre 2000StatutMembreDernière intervention 3 mars 20097 17 mai 2007 à 10:04
En fait, la fonction Contains d'une collection recherche un objet de la collection selon sa clé, or tu n'affecte pas de clé à ces objets, il est donc normal qu'il renvoie toujours False.
Tu pourrais affecter une clé à chaque c, mais ca ne me semble vraiment pas être l'idéal vu que tu connais le nombre d'élément total de ton graphe. Fais plutot un tableau 10X10 (comme adj) de boolean qui seront par défaut à False et que tu mets à True lorsqu'ils sont utilisés :
Dim marque(9,9) as Boolean
...
If adj(start, c) = 1 And not marque(start, c) Then
marque(start, c) = True
...
Sinon, pourquoi définis-tu adj comme un tableau d'objets et non un tableau de double, voir même d'entiers pour une matrice d'adjacence ?
Et aussi, tu pourrais utiliser des listes typées (As New List(Of ...)) à la place des collections, ça à l'avantage d'être plus maniable et d'être... typé :)