J'ai un problème qui peut essentiellement être vu sous forme de graphique. J'envisage d'utiliser JGraphT pour l'implémenter au lieu de lancer le mien. Quel serait le meilleur moyen d'obtenir un arbre couvrant minimum d'un graphique en utilisant JGraphT?Java: Spanning minimal avec JGraphT?
Malheureusement, je ne connais pas assez la théorie des graphes pour vous donner une réponse complète et directe, mais j'ai utilisé jgrapht dans quelques projets, alors peut-être que cela vous aidera.
La liste des algorithmes inclus JGraphT est ici: http://www.jgrapht.org/javadoc/org/jgrapht/alg/package-summary.html, et vous pouvez également trouver traversals graphique implémenté itérateurs (si cela est une aide) ici: http://www.jgrapht.org/javadoc/org/jgrapht/traverse/package-summary.html
Je suis sûr qu'aucun de ces algorithmes seront Si vous voulez que vous vouliez sortir de la boîte, vous devrez le coder vous-même, mais je peux vous dire par expérience que le codage au-dessus de jgrapht plutôt que de partir de zéro est BEAUCOUP plus facile. Il y a aussi une classe FibonacciHeap qui aiderait vraisemblablement à implémenter l'algorithme de Prim.
Si vous avez besoin d'aide avec l'algorithme lui-même, il existe un certain nombre d'algorithmes avec des entrées Wikipedia, avec des descriptions détaillées et pseudocode. Les liens Minimum spanning tree article à eux.
Jung a une implémentation de ceci.
ClosestFirstIterator peut vous aider. Il construit un arbre couvrant en utilisant FibonacciHeap en itérant sur les sommets. ClosestFirstIterator fournit les méthodes getShortestPathLength() et getSpanningTreeEdge() pour obtenir des parties de l'arbre recouvrant minimal.
// instantiate the iterator
ClosestFirstIterator<V,E> it = new ClosestFirstIterator<V,E>(graph, start_vertex);
// iterate to build the tree
while(it.hasNext())
it.next();
// query
double distance = getShortestPathLength(vertex);
E next_edge = getSpanningTreeEdge(vertex);