Discussion :

[infofree]

bonjour
j'ai un tableau a 2 dimensions contenant les différentes arêtes d'un graphe

exemple : [(1,2) ; (1,3) ; (2,3) ; (2,4) ; (2,5) ; (3,1) ; (3,4)]

j'ai aussi le tableau des sommets de ce graphe [1,2,3,4,5]

je souhaite implémenter l'algorithme de Kruskal pour tester la connexité de ce graphe , mais je ne sais pas du tout comment procéder.
je demande pas le programme entier, mais juste des pistes pour me guider
merci

[jhaythem]

tu peux ecris l algorithme de Kruskal ici? ca te donneras les etapes a faire...
et pour le code c est pas complique.

[19cmos83]

'lut,

Algo de Kruskal

KRUSKAL (G,w)
1 E := ø
2 pour chaque sommet v de G
3 faire CRÉER-ENSEMBLE (v)
4 trier les arêtes de G par ordre croissant de poids w
5 pour chaque arête (u,v) de G prise par ordre de poids croissant
6 faire si ENSEMBLE-REPRÉSENTATIF (u) ≠ ENSEMBLE-REPRÉSENTATIF (v)
7 alors ajouter l'arête (u,v) à l'ensemble E
8 UNION (u,v)
9 retourner E


w est une fonction qui associe à chaque arête du graphe G une valeur qui est son poids. La fonction ENSEMBLE-REPRÉSENTATIF(e) retourne un élément représentatif d'un ensemble. UNION(u,v) combine les arbres obtenus au fur et à mesure.

La complexité de l'algorithme est Θ(A log S) avec A le nombre d'arêtes et S le nombre de sommets du graphe G. Lors du déroulement de l'algorithme, l'ACM n'est pas connexe, il ne le sera qu'à la fin.

[infofree]

bon je vois a peu pres l'algo
sachant que maintenant j'ai une classe Arete qui contient le sommet de depart, le sommet d'arrivée, et le poids affecté

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
class Arete
	{ public Arete(int pointA, int pointB,int poids)
		{
		this.pointA=pointA; this.pointB=pointB; this.poids=poids;
		}
	 public void affiche()
		{
		System.out.print("arc du sommet : "+pointA + " au sommet : "+pointB+" " ) ;
		}
 
	private	int pointA, pointB, poids;
	}

je souhaite maintenant trier ces arcs par ordre croissant des "poids" , y'a t'il une methode simple pour le faire? j'ai pensé à "Arrays.sort" mais il me semble qu'il prend comme argument des tableaux, or là j'ai affaire à une classe (enfin, à un objet )

[CheryBen]

Bonjour, il fuat effectivement utiliser Arrays.sort(T[] a, Comparator<? super T> c).
Cette méthode prendra en arguments un tableau d'Arete et un Comparateur d'Arete (une classe qui implémente l'interface Comparator).
Dans ce comparateur tu dois implémenter les méthodes compare et equals, qui comparerons les poids des Arete.