Есть ли простой способ перечислить все связующие деревья косвенного графа? Это может иметь сложность O (2^n). Количество узлов на графике всегда ниже 10. Я знаю, что у Кнута есть алгоритм на томе 4 TAoCP, но я не могу его найти.Алгоритм для перечисления всех связующих деревьев графа
Есть другие работы в литературе, вы их проверили? Сначала алгоритм Char, который описан в [Jayakumar et al.'84]. Там же алгоритм [Kapoor & Ramesh'91], который подробно описан в своей статье, и работа [Postnikov'94]
Кроме того, вы можете посмотреть на эту другую протектором: Find all spanning trees of a directed weighted graph (некоторые ответы уже неориентированных графов).
Наконец, обратите внимание, что даже если алгоритмическая сложность очень высока, это может быть не проблема на практике, на таком маленьком графике.