Algorithme de coloration de graphe (coloration Greedy)

Question

Je travaille sur un projet de coloration de graphe utilisant Java. J'ai besoin de mettre en œuvre quatre algorithmes de coloration de graphe différents en utilisant le théorème de quatre couleurs. J'ai un problème avec l'un des algorithmes nommés quelques voisins algorithme cupide.

J'ai une carte qui contient des tas d'objets polygones (stockés dans une liste de tableaux). En outre, j'ai un tableau booléen 2D qui représente les adjacences de différents polygones.

Je connais théoriquement l'algorithme: J'ai une file d'attente prioritaire qui stocke mes polygones non colorés. L'ordre de la file d'attente basé sur les comptages d'adjacence. Si un polygone a peu de voisins, il est considéré comme meilleur qu'un polygone qui a beaucoup de voisins. Quoi qu'il en soit, l'algorithme devrait à plusieurs reprises dessiner un polygone à partir de la file d'attente prioritaire et essayer de le colorer en fonction de ses adjacences.

Malheureusement, j'ai des problèmes avec la partie implémentation. J'ai eu la file d'attente prioritaire basée sur les comptes d'adjacence, mais j'ai des problèmes en assignant des couleurs à ces polygones. Si quelqu'un a travaillé sur ce genre d'algorithmes, ou si quelqu'un a une idée, n'hésitez pas à partager avec moi. J'ai besoin d'idées pour accélérer la mise en œuvre.

Merci d'avance.

Answer 1

Vous devez indiquer exactement le type d'aide dont vous avez besoin avec la partie implémentation. "J'ai des problèmes lors de l'attribution des couleurs" comment?

Une carte qui contient des objets polygones stockés dans une liste de matrices avec un tableau booléen 2D séparé pour les adjacences est l'entrée? Je suppose que vos polygones sont des nœuds dans le graphique.

Vous devez probablement créer une structure de données graphique et la parcourir. L'approche classique de style C utilise des tableaux pour les nœuds et les arêtes et making it look complex.

Depuis OOP using Composition génère naturellement un graph of objects c'est une bonne approche à utiliser ici.

Les graphes sont essentiellement composés de 2 éléments: les nœuds et les arêtes.

Commencez par une classe de noeud. Il a une couleur, un identifiant et une ArrayList of Edges. Les arêtes forment une relation entre deux nœuds et peuvent avoir un poids et une direction. Faites les noeuds et les arêtes à partir des entrées (rappelez-vous, si un nouveau noeud n'existe pas, faites-le). Ensuite, exécutez le nearest neighbor algorithm en choisissant un nœud non marqué (une méthode statique peut bien fonctionner pour cela, ou vous pouvez vraiment pratiquer pour la vie réelle et mettre en œuvre le modèle de stratégie).

Attention aux cycles!

Answer 2

Vous semblez que vous essayez de colorer les nœuds les plus bas en premier. Cela semble en arrière, vous devriez colorier les nœuds les plus élevés en premier. Par exemple, les nœuds de degré 3 seront toujours colorables si vous avez le choix entre 4 couleurs.

Vous vous rendez compte que tout algorithme glouton pourrait très bien ne pas trouver un 4-color, même si le graphique est 4 couleurs.

Consultez le Wikipedia page pour des pointeurs utiles.