algorithme de Kruskal

bonsoir a vous tous. je développe un petit logiciel me permettant de vérifier mes résultats en recherche operationnelle mais je bute sur l’algorithme de kruskal.

le problème ce trouve au niveau de montrer que le graphe est acyclique.

j’avais implémenter un truc simple me permettant de prouver ça mais ça ne suffit pas. je vous explique: si je prends l’arête (A, B) et l’arête (B, C) je sais automatiquement que l’arête (A, C) ne doit pas exister sinon on a un cycle. Mais il peut avoir ce cas la on prends (A, B) (D, C) (B, C) en suivant le même principe que ci-dessus je sais que (A, C) et (D, B) ne doivent pas exister sinon on a un cycle. Mais aussi (A, D) mais a ce stage mon algorithme ne le sait pas donc si on le prend on aura un cycle quelque soit le nombre de sommet.

Pouvez vous m’aider a trouver un algorithme me permettant de montrer qu’un graphe est acyclique ou non.

Merci d’avance .

1) Tu rajoutes tous les sommets des arrêtes que tu as sélectionées dans une liste.

2)Tu crées un cycle en ajoutant un arrete si les 2 sommets de cette arrête sont dans la liste des sommets précédente.

3) Tu prends une arrete, s’il y a 0 ou 1 sommet dans la liste des sommets alors tu ajoutes le sommets (ou les 2 dans le cas de 0) à la liste précédente. Sinon, tu prends l’arrete suivante.

Par exemple si tu as (A,B) (D,C) et (B,C). Ta liste ressemble à [A,B,C,D]
Donc tu ne peux pas prendre (A,D) car A et D sont dans la liste. Ni (A, C) pour la même raison.
Par contre, tu peux prend (A,E)
Ta liste devient alors : [A,B,C,D,E].
…

PS: Je n’ai pas préciser mais dans le cas de 2, c’est plus compliqué il faut faire ça pour chaque ensemble connexe -_- …

Du coup, je modifie ma réponse car s’il faut gérer les parties connexes mieux vaut t’aider un peu : Tu utilises un index.
A -> 0
B -> 1
C -> 2
…

Au début chaque sommets est une partie connexe que tu va étiqueté d’un numéro.
[0, 1, 2, 3, 4, 5, 6]
A, B, C, D, E, F, G
Tu va ajouter l’arrète (A,B). Donc inter-connecté la partie connexe 0 et 1.
S’ils ont la même étiquette alors rajouter l’arrète forme un cycle.
Sinon, tu reprends la liste pour la transphormer ainsi :
[0, 0, 2, 3, 4, 5, 6]

Donc maintenant tu ajoutes l’arrète (C,D)
Ton jeu deviens :
2 != 3 donc pas de cycle.
[0, 0, 2, 2, 4, 5, 6] # On tranphorme l’étiquette de valeur maximum en celle de valeur minimum (ou le contraire peut importe il faut juste rester cohérent.

On ajoutes (B,C)
0 != 2 donc pas de cycle.
[0, 0, 0, 0, 4, 5, 6]

On ajoute (A,D)
[0, 0, 0, 0, 4, 5, 6]
0 == 0 donc crée un cycle.

Détecter un cycle ne peut pas se faire avec un simple parcours en largeur/profondeur ou une combinaison des deux ? (Je ne sais plus le terme exacte, c’est un peu loin)
Il me semblait que détecter un cycle est facile, ce qui est difficile c’est d’en chercher un d’une longueur donnée.

Merci Ache je vais essayer les deux pour voir. Merci beaucoup

Détecter un cycle dans un graphe orienté est plutôt simple, non ? Un parcours en profondeur où on sauvegarde dans une liste chaque sommet visité durant le parcours courant. (Évidemment, on pop le dernier sommet visité et démarque comme viité dès lors qu’on remonte d’un niveau de profondeur pour passer au sommet suivant)

Si le sommet qu’on visite actuellement est dans cette liste, cela implique un cycle.

Et tu fais ce parcours pour chaque sommets "racines" possibles.

Ache je voudrais savoir si je dois combiner les deux ou utiliser un. Parce que j’ai utilisé le deuxième et je suis tomber sur un cycle. Merci

Seul le deuxième est correcte en fait …

Essaye tu peux nous montrer ton code ?

Je n’ai pas encore écrit le code mais j’ai essayé avec un exemple et j’ai trouver un cycle voici l’exemple : On n’a

(A B 35) (A D 40) (B C 10) (B D 25) (C D 20) (C E 30) ET (D E 15).

voici le graphe .on a l’arête et puis sa longueur donc on a l’arête (A B) qui a une longueur de 35 pareil pour les autres. Je veux l’arbre couvrant minimal.

En appliquant ton algorithme j’ai:

[0,1,2,3,4,]

[A,B,C,D,E]

Je prends l’arête (B, C) qui a une longueur de 10 On a 1!=2 pas de cycle Donc on obtient

[0,1,1,3,4]

Je prends l’arête (D E) qui a une longueur de 15

Donc on obtient

[0,1,1,3,3]

Je prends l’arête (C D) qui a une longueur de 20

On a 1!=3 donc pas de cycle

On obtient [0,1,1,1,3]

Je prends l’arête (B D) qui a une longueur de 25 On a 1=1 on a un cycle Donc on ne prend pas.

Je prends l’arête (C E) qui a une longueur de 30 On a 1!=3 donc pas de cycle

Or si on la prends elle forme un cycle.

Merci