[Graphe] Affecter une même valeur au nœuds reliés par un chemin

Marsh Posté le 24-10-2011 à 22:20:34

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". En gros, ça revient à associé le même label à tous les nœuds d'une même composante connexe.

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.

Edit:

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

Code :

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;
}
}

Message édité par charlebakhtovsky le 24-10-2011 à 23:48:01

Marsh Posté le 24-10-2011 à 22:20:34

Marsh Posté le 24-10-2011 à 23:53:33

Bon apparemment ça marche donc problème résolu.

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed

Name *

Email *

URL

Message *