Discussion :

[klandah]

Bonjour,

J'ai un graphe non orienté. Pour visualiser les résultats de certains traitements, j'ai besoin d'affecter une même valeur (étiquette) à tous les nœuds qui sont reliés par un chemin. Il y aura donc des blocs de "nœuds ayant une même étiquette".

L'idée c'est que tant qu'il reste des nœuds non étiquetés:
Prendre un nœud non étiqueté et lui affecté une étiquette (valeur). Puis affecter la même étiquette à tous les nœuds non étiquetés, connectés à ce nœud par un chemin.

Mais algorithmiquement, je bloque un peut.
Des propositions ?

Merci bien.

[kwariz]

Hello,

si le graphe est non orienté cela revient à associé le même label à tous les noeuds d'une même composante connexe.

[klandah]

Hello,

si le graphe est non orienté cela revient à associé le même label à tous les noeuds d'une même composante connexe.

Ben oui, c'est ce que je demande en gros. ça se fait de façon récursive ?

[kwariz]

Oui, pour labéliser tes sommets tu fais un parcours à partir d'un sommet non marqué en marquant les sommets traversés, et tu le fais tant qu'il reste des sommets non marqués. Tu trouveras facilement des implémentations et des algos sur le net.

[klandah]

Oui, pour labéliser tes sommets tu fais un parcours à partir d'un sommet non marqué en marquant les sommets traversés, et tu le fais tant qu'il reste des sommets non marqués. Tu trouveras facilement des implémentations et des algos sur le net.

Pensez-vous que ma solution ci-dessous est cohérente ?

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
Procedure Etiquetage(Noeud N, int i)
{
   N.etiquette = i;
   Pour chaque voisin NV de N faire:
   {
      Si NV.etiquette n'existe pas alors:
      {
         Etiquetage(NV, i);
      }
   }		
}
 
int i = 0;
Pour chaque noeud N du graphe:
{
   Si N.etiquette n'existe pas alors:
   {
      Etiquetage(N, i);
      i = i + 1;
   }
}

[kwariz]

Oui, ça m'a l'air pas mal du tout