Algorithme de Bron-Kerbosch pour la recherche de clique
Quelqu'un peut me dire, où sur le web je peux trouver une explication à Bron-Kerbosch algorithme pour la clique de trouver ou de l'expliquer ici comment cela fonctionne?
Je sais qu'il a été publié dans "l'Algorithme 457: trouver toutes les cliques d'un graphe non-dirigé" livre, mais je ne trouve pas de source libre qui va décrire l'algorithme.
Je n'ai pas besoin d'un code source de l'algorithme, j'ai besoin d'une explication de la façon dont il fonctionne.
source d'informationauteur Alex Reitbort | 2008-09-27
Vous devez vous connecter pour publier un commentaire.
Essayer de trouver quelqu'un avec un ACM compte de l'étudiant qui peut vous donner une copie de la feuille de papier, qui est ici: http://portal.acm.org/citation.cfm?doid=362342.362367
J'ai juste téléchargé, et cela ne fait que deux pages, avec une mise en œuvre dans l'Algol 60!
je trouve l'explication de l'algorithme ici: http://www.dfki.de/~neumann/ie-séminaire/présentations/finding_cliques.pdf
c'est une bonne explication... mais j'ai besoin d'une bibliothèque ou de la mise en œuvre en C# -.-'
Il est l'algorithme de droit ici j'ai réécrit à l'aide de Java linkedlists que les ensembles R,P,X et il fonctionne
comme un charme (s bonne chose est d'utiliser la fonction "retainAll" lorsque vous effectuez des opérations définies en fonction de l'algorithme).
Je vous suggère de réfléchir un peu sur la mise en œuvre en raison des problèmes d'optimisation lors de la réécriture de l'algorithme
J'ai également essayer d'envelopper ma tête autour de l'Bron-Kerbosch algorithme, donc j'ai écrit ma propre implémentation en python. Il comprend un test et quelques commentaires. Espérons que cette aide.
Pour ce qu'il vaut, j'ai trouvé une implémentation de Java: http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup
HTH.
J'ai mis en œuvre les deux versions spécifié dans le document. J'ai appris que, le unoptimized version, si elle est résolue de manière récursive aide beaucoup à comprendre l'algorithme.
Voici python de mise en œuvre pour la version 1 (unoptimized):
Et vous appelez cette fonction:
La variable
cliques
contiendra cliques trouvé.Une fois que vous comprenez cela, il est facile à mettre en œuvre optimisé.
Boost::Graphique a une excellente mise en œuvre de Bron-Kerbosh algorithme, de lui donner un chèque.