Discussion :

[edenroad]

Bonjour,
Voici mon problème :
Je développe un programme qui permet la création de graphs non orientés.
A partir de ces graphs je créé une matrice d'adjacence triangulaire supérieure car dans mon cas, un sommet ne peut être relié à lui même, et si deux sommets sont reliés par plusieurs arrêtes cela équivaut à une seule arrête.
C'est donc une matrice très simple.

Je cherche un algorithme permettant de récupérer les différents "compartiments" du graph.
C'est à dire une liste par groupe de sommets reliés, car il est possible qu'il y ai des parties du graph non reliées à d'autres parties.

J'ai du mal à formuler ma demande sur les moteurs de recherche (manque de terminologie en théorie des graphs).
Si vous avez des pistes ou même un nom d'algorithme je suis preneur !

Merci beaucoup

[picodev]

Bonjour,

Tu cherches les composantes connexes. Pour les déterminer tu peux faire un parcours en profondeur (depth first search, DFS). De nombreux algorithmes nécessitent un parcours soit en profondeur, soit en largeur il va falloir te familiariser non seulement avec le vocabulaire mais aussi avec les algorithmes de base.

[tbc92]

Une procedure comme celle-ci devrait faire l'affaire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
Procedure sousgroupe ( Nombre_de_sommets,  tableau_d_aretes)
Nbre_aretes = dimension ( tableau_d_aretes)
 
TABLO est un tableau de Nombre_de_sommets entiers
 
Pour i = 1 a nombre_de_sommets
   tablo[i] = i    // Tableo va donner un numéro de groupe pour chaus sommet. Au départ, les numero de groupe sont tous différents.
fin
 
Pour i = 1 a Nbre_aretes
   extremite_1 = sommet_1 ( tableau_d_aretes[i] )
   extremite_2 = sommet_2 ( tableau_d_aretes[i] )
   i1 = tablo[extremite_1]
   i2 = tablo[extremite_2]
   si i1 = i2  
     // Rien à faire, on avait déjà un réseau d'arêtes qui reliait nos 2 extrémités.
  sinon
      si i1 > i2 alors    // je permute i1 et i2 pour avoir i1 < i2
         tmp = i1
         i1 = i2
         i2 = tmp    
     fin
     //  Quand une arête relie 2 groupes de numéros i1 et i2, avec i1 < i2, je dis que tous les points qui étaient dans i2 sont en fait dans i1 
     //   En fait, chaque groupe est identifié par l'indice le plus petit de tous les éléments de ce groupe.
     Pour j = 1 a nombre_de_sommets
         si tablo[j] = i2 alors tablo[j] = i1
     fin
fin

A la fin de cette boucle, Pour 2 sommets S1 et S2, si tablo[s1] = tablo[s2] , c'est qu'on peut les relier par une succession d'arêtes.

C'est un bout de pseudo-code improvisé, mais je suis totalement confiant.
Par contre, comment ça s'appelle, ça n'a pas de nom particulier, je n'ai pas déposé de brevet.

[edenroad]

Bonjour à tous et merci pour vos réponses.
J'ai finalement trouvé une solution ce matin qui n'utilise pas cette matrice (car j'ai un niveau moyen en maths ahah)

Si ça peut en aider certain voici ce que j'ai fait :
Je pars d'une liste d'arretes et d'une liste de sommets.
Je créé une liste de sommet vide qui contient tous les sommets que j'ai déja traité (pour ne pas les retraiter).

je parcours les sommets de la liste initiale et pour chaque sommet je fais une recursivité pour chaque arrete de ce sommet en ajoutant tous les sommets trouvés a la liste deja traité et au compartiment du sommet de la premiere liste. Code c++ utilisant des CPtrList

Code c++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
 
CListOfSommets* dejaTries = new CListOfSommets;
int i,j;
for (i=0;i<listeSommets->GetCount();i++)
{
	CSommet* pSommet = listeSommets->Item(i);
        // Cas de sommet considéré comme n'étant pas une liaison (peut changer au cours de l'application)
	if (pSommet ->bloquant())
	{
		CZone* pZone= new CZone();
		pZone->AddTail(pSommet );
		dejaTries->AddTail(pSommet);
		zones->AddTail(pZone);
		continue;
	}
	// On verifie que le sommet n'a pas deja été traité
	if (sommetInListe(dejaTries, pSommet)) continue;
        // On fait la recursivite
	CZone* pZone= new CZone();
	pZone->AddTail(pSommet);
	dejaTries->AddTail(pSommet);
	nouvelleZone(pSommet , pZone, dejaTries);
	zones->AddTail(pZone);
}
 
 
void MaClasse::nouvelleZone(CSommet* pSommet, CZone* pZone, CListOfSommets* dejaTries)
{
	int i;
	for (i=0;i<listeArretes->GetCount();i++)
	{
		CSommet* pSommetSuivant = NULL;
		CArrete* pArrete = listeArretes->Item(i);
		// Pas de "faux" lien (spécificité de mon app)
		if (pArrete->bloquant()) continue;
		if (pArrete->begin == pOp)
		{
			pSommetSuivant = pArrete->end;
		}
		else if (pArrete->end == pOp)
		{
			pSommetSuivant = pArrete->begin;
		}
                // Si ce lien ne correspond pas au sommet en cours on passe au suivant
		if (!pSommetSuivant) continue;
		// Si ce sommet est deja traité on passe au suivant
		if (operationInListe(dejaTries, pSommetSuivant)) continue;
		pZone->AddTail(pSommetSuivant);
		dejaTries->AddTail(pSommetSuivant);
		nouvelleZone(pSommetSuivant, pZone, dejaTries);
	}
 
}

EDIT : typo

[picodev]

Tu viens de redécouvrir plus ou moins le parcours en largeur …
Je ne peux que te conseiller de te familiariser avec le vocabulaire de la théorie des graphes ainsi que des algorithmes de base.
Cela te permettra non seulement de savoir quoi chercher mais aussi d'avoir une réflexion adaptée à ce genre de structure de donnée.
N'oublie pas de passer le sujet en résolu.

[dourouc05]

Tu as déjà ici quelques ressources sur les graphes : http://lapoire.developpez.com/algorithmique/graphes/, http://tcuvelier.developpez.com/tuto...-donnees/#LVII.