Création d'un arbre de recouvrement à l'aide de BGL

Question

J'ai un graphe BGL et je souhaite créer un arbre de recouvrement en utilisant BGL.

À partir d'un sommet spécifié, je souhaite ajouter le plus petit tronçon à mon graphique qui se connecte à ce sommet. A partir de là, je veux toujours choisir le bord le plus court qui se connecte au graphique qui existe jusqu'à présent. Donc, je veux ajouter la contrainte que chaque nouvelle arête doit être connectée au graphe déjà tout en restant avec le critère de l'arbre de recouvrement qu'il n'y a pas de cycles.

Il ne serait pas très difficile de le faire à la main; mais puisque je veux apprendre quelque chose sur BGL, j'aimerais savoir quel algorithme convient le mieux à mon problème.

Answer 1

Il semble que vous développez un arbre, en commençant par le sommet spécifié, en ajoutant le bord le plus léger qui connecte un sommet dans votre arbre à un sommet qui n'est pas dans votre arbre. Si c'est le cas, vous implémentez l'algorithme de Prim, qui vous donne un MST. Il est bien décrit dans le chapitre MST de "Algorithms" par Cormen, Leiserson, Rivest & Stein.

(Je dis "ressemble à" parce que l'énoncé "le bord le plus court qui se connecte au graphique qui existe jusqu'à présent" est un peu vague.)

Answer 2

C'est l'algorithme Prim: http://en.wikipedia.org/wiki/Prim%27s_algorithm

Vous obtiendrez un arbre minimum!

Vous ne savez pas si vous allez en tirer un BGL, mais de toute façon, ce qui est difficile dans cette idée, c'est de trouver le "minimum edge": regardez le pseudo-code sur la page wikipédia pour voir comment ça se fait en utilisant un tas binaire. Pour une meilleure complexité, vous aurez besoin de tas de Fibonacci.