Kruskal - en console
Description
Bonjour,
Kruskal permet d'établir le chemin le moins couteux en reliant tous les points d"un graphe
Son fonctionnement est simple, il faut
il faut trié les connexions dans l'ordre croissant
relié les villes entre elle selon cette ordre.
mais pour ne pas relier deux fois la même ville et de ne pas avoir un arbre à cout minimum, j'ai utilisé le principe de couleur ( poids / valeur) pour détecter si deux villes ou deux était reliés ensembles. deux couleurs différentes alors on peut relier sinon la connexion est déjà faites.
J'ai réalisé l'algo de Kruskal pas pour sa complexité mais pour mettre en place le système de couleur.
Dans le dossier Release du ZIP il y a un fichier text (cf. "kruskal.txt") qui correspond à l'exemple mis sur wikipédia.
kruskal.exe << kruskal.txt pour éviter les saisies
Kruskal permet d'établir le chemin le moins couteux en reliant tous les points d"un graphe
Son fonctionnement est simple, il faut
il faut trié les connexions dans l'ordre croissant
relié les villes entre elle selon cette ordre.
mais pour ne pas relier deux fois la même ville et de ne pas avoir un arbre à cout minimum, j'ai utilisé le principe de couleur ( poids / valeur) pour détecter si deux villes ou deux était reliés ensembles. deux couleurs différentes alors on peut relier sinon la connexion est déjà faites.
Source / Exemple :
Option Explicit On
Option Strict On
Imports System
Module Kruskal
Structure connect
Dim ville_deb As String
Dim ville_fin As String
Dim valeur As Integer 'Corresponds à une couleur suite à une liaison (cf. la méthode de Kruskal plus bas)
End Structure
Structure village
Dim nom_ville As String
Dim etat As Integer
End Structure
Dim ville(0 To 0) As village ' Tableau comportant les noms des villes
Dim connexion(0 To 0) As connect ' Tableau des poids des liaisons entre les villes
Dim resul(0 To 0) As connect ' Tableau comportant les résultats
Sub Main()
Dim a As String ' Variable d'acquisition
Console.Out.WriteLine("Programme de Kruskal en VB.NET")
Console.Out.WriteLine()
Console.Out.Write("Saisir le Nbr de ville = ")
a = Console.In.ReadLine
If IsNumeric(a) Then " on test si a est bien numérique pour éviter les plantages
Dim ptr2 As Integer
Dim nbr_ville As Integer
ptr2 = 0
nbr_ville = CInt(a)
If nbr_ville > 1 Then
Console.Out.WriteLine()
Console.Out.WriteLine("Saisir les liaisons sous la forme suivante :")
Console.Out.WriteLine("Ville d'origne / valeur de la connexion,ville d'arrivée / ...")
nbr_ville = nbr_ville - 1
ReDim ville(0 To nbr_ville)
ReDim connexion(0 To 0)
For ptr As Integer = 0 To nbr_ville
Dim nom_ville As String
Dim nfo() As String
Dim mx As Integer
' Récupération de données
a = Console.In.ReadLine
a = Replace(UCase(a), " ", "")
nfo = Split(a, "/")
nom_ville = nfo(0)
mx = UBound(nfo)
For num As Integer = 1 To mx
Dim nfo2() As String
Dim ville_fin As String
Dim valeur_connexion As String
ReDim Preserve connexion(0 To ptr2)
nfo2 = Split(nfo(num), ",")
valeur_connexion = nfo2(0)
ville_fin = nfo2(1)
If IsNumeric(valeur_connexion) Then
connexion(ptr2).ville_deb = nom_ville
connexion(ptr2).ville_fin = ville_fin
connexion(ptr2).valeur = CInt(valeur_connexion)
ptr2 = ptr2 + 1 ' on prévoit un futur emplacement dans le tableau des connexions
End If
Next
ville(ptr).etat = ptr ' couleur de la ville
ville(ptr).nom_ville = nom_ville ' nom de la ville
'connexion(0, ptr) = ""
Next
' Fin de la partie acquisition des données
' http://fr.wikipedia.org/wiki/Algorithme_de_Kruskal
' tri du tableau des connexion par valeur
' (normal c'est un Quicksort mais j'ai fait au plus simple donc un tri en N²)
' On srcute avec 2 pointeurs la table et on inverse selon la condition souhaité.
Dim mx2 As Integer
mx2 = UBound(connexion)
For ptr As Integer = 0 To mx2 - 1
For ptr3 As Integer = ptr + 1 To mx2
Dim mem As connect
If connexion(ptr3).valeur < connexion(ptr).valeur Then
mem = connexion(ptr)
connexion(ptr) = connexion(ptr3)
connexion(ptr3) = mem
End If
Next
Next
' on affiche le résultat de tri
System.Console.Out.WriteLine()
For ptr As Integer = 0 To UBound(connexion)
System.Console.Out.Write(connexion(ptr).ville_deb & " + ")
System.Console.Out.Write(connexion(ptr).ville_fin & " = ")
System.Console.Out.Write(Str(connexion(ptr).valeur))
System.Console.Out.WriteLine()
Next
ReDim resul(0 To nbr_ville - 1)
' Kruskal
ptr2 = 0
For ptr As Integer = 0 To UBound(connexion)
' Ville_OK permet de tester si deux sont déjàs reliés ou NON
If Ville_OK(connexion(ptr).ville_deb, connexion(ptr).ville_fin) Then
resul(ptr2) = connexion(ptr) ' on stocke la connexion qui a été retenu dans le tableau des résultats
' En suite il faut controler s'il n'y a pas des groupes de villes qui se serait connectés avec la nouvelles branches.
' et si c'est le cas changer les couleurs (valeur) des villes de l'un des groupes.
For ptr3 As Integer = 0 To ptr2
If resul(ptr3).ville_deb = connexion(ptr).ville_deb _
Or resul(ptr3).ville_deb = connexion(ptr).ville_fin _
Or resul(ptr3).ville_fin = connexion(ptr).ville_deb _
Or resul(ptr3).ville_fin = connexion(ptr).ville_fin Then
ville(num_ville(resul(ptr3).ville_deb)).etat = ville(num_ville(connexion(ptr).ville_deb)).etat
ville(num_ville(resul(ptr3).ville_fin)).etat = ville(num_ville(connexion(ptr).ville_deb)).etat
ville(num_ville(connexion(ptr).ville_fin)).etat = ville(num_ville(connexion(ptr).ville_deb)).etat
End If
Next
ptr2 = ptr2 + 1
End If
If ptr2 = nbr_ville Then
ptr = UBound(connexion)
End If
Next
'Affichage du résultats
System.Console.Out.WriteLine()
System.Console.Out.WriteLine("Résultat")
For ptr = 0 To nbr_ville - 1
System.Console.Out.Write(resul(ptr).ville_deb & " + ")
System.Console.Out.Write(resul(ptr).ville_fin & " = ")
System.Console.Out.Write(Str(resul(ptr).valeur))
System.Console.Out.WriteLine()
Next
'a = Console.In.Read()
System.Console.Out.WriteLine()
a = Console.In.ReadLine
System.Console.Out.Write(a)
End If
End If
Console.Out.WriteLine()
Console.Out.WriteLine("Quit Ctrl+C")
a = Console.In.ReadToEnd
End Sub
Private Function Ville_OK(ByVal v1 As String, ByVal v2 As String) As Boolean
Dim rsl As Boolean
' Si les deux villes ont la même couleur alors l'une des deux villes prend la couleur de l'autre
If ville(num_ville(v1)).etat = ville(num_ville(v2)).etat Then
rsl = False ' cas où les villes sont déjàs reliés
Else
rsl = True ' cas où l'on doit reliés les villes
ville(num_ville(v2)).etat = ville(num_ville(v1)).etat
End If
Ville_OK = rsl
End Function
Private Function num_ville(ByVal nfo As String) As Integer
' permet de convertir le nom de la ville en numéro de position dans le tableau "ville"
Dim mx, ptr As Integer
mx = 0
For ptr = 0 To UBound(ville)
If ville(ptr).nom_ville = nfo Then
mx = ptr
ptr = UBound(ville) ' permet de sortir du for une fois la valeur trouvé
End If
Next
num_ville = mx
End Function
End Module
Conclusion :
J'ai réalisé l'algo de Kruskal pas pour sa complexité mais pour mettre en place le système de couleur.
Dans le dossier Release du ZIP il y a un fichier text (cf. "kruskal.txt") qui correspond à l'exemple mis sur wikipédia.
kruskal.exe << kruskal.txt pour éviter les saisies
Codes Sources
A voir également
- Kruskal - en console
- C# console pause ✓ - Forum C# / .NET
- Visual studio console - Forum C# / .NET
- Kruskal ✓ - Forum C
- C++ clear console ✓ - Forum C / C++ / C++.NET
- Console visual studio ✓ - Forum C# / .NET
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.