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
FORUM HardWare.fr
