Kruskal - en console

Soyez le premier à donner votre avis sur cette source.

Vue 4 153 fois - Téléchargée 214 fois

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.

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

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.