Dupliqué possible:
Tout au minimum s'étendant sur la mise en œuvre des arbresComment puis-je trouver tous les arbres minimum étendus dans un graphique non dirigé de manière efficace?
3 Réponses :
excuses pour la réponse académique ... mais algorithme s dans Knuth's TAOCP , volume 4, fascicule 4 est exactement à propos de générer tous les arbres étendus (pp. 26ff). Il y a quelques Musingings quand il parle de générer des arbres (étendues) , mais votre meilleur pari dans TAOCP.
Vous pouvez en trouver un..MOdifier l'algorithme BFS!
Oui, il y a algorithmes pour générer tous les arbres étendus dans un graphique. Au moins Un comprime la sortie en générant uniquement des diffs entre les arbres. Comme d'autres l'ont souligné, il pourrait y avoir beaucoup d'arbres au minimum étendu pour même un petit graphique.
Remarque Le nombre d'arbres étendus minimum peut être exponentiel dans la taille du graphique. Vous ne voulez probablement probablement pas les renvoyer tous.
@Keith Knuth a écrit une toute book sur des arbres énumérants dans les graphiques. Ce n'est pas parce que vous avez un numéro exponentiel de quelque chose que vous ne voulez pas tous les voir tous. Dans ce cas, cela signifie simplement que ce n'est pas pratique, alors voyez-les tous pour un graphique général général.