Учитывая ненаправленный граф, я хочу сгенерировать все подграфы, которые являются деревьями размера N, где размер относится к числу ребер в дереве.
Я знаю, что тамих много (экспоненциально много, по крайней мере, для графов с постоянной связностью) - но это нормально, так как я считаю, что число узлов и ребер делает это возможным по крайней мере для небольших значений N (скажем, 10 или меньше).
Алгоритм должен быть эффективным для памяти, то есть не должен иметь в памяти все графики или некоторое большое их подмножество одновременно, поскольку это может превысить доступную память даже для относительно небольших графиков.Поэтому желательно что-то вроде DFS.
Вот что я думаю в псевдокоде, учитывая начальный граф graph и желаемую длину N:
Выберите любой произвольный узел,root в качестве отправной точки и вызов alltrees(graph, N, root)
alltrees(graph, N, root)
given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think)
for each tuple (X1, X2, ... XM) above
create a subgraph "current" initially empty
for each integer Xi in X1...XM (the current tuple)
if Xi is nonzero
add edge i incident on root to the current tree
add alltrees(graph with root removed, N-1, node adjacent to root along edge i)
add the current tree to the set of all trees
return the set of all trees
Это находит только деревья, содержащие выбранный начальный корень, поэтому теперь удалите этот узел и вызовите все дерево (граф с удаленным корнем, N, новый произвольно выбранныйroot), и повторяйте до тех пор, пока размер оставшегося графа
Я также забыл, что каждый посещенный узел (каждый корень для некоторого вызова всех деревьев) долженбыть отмеченным, и набор детей, рассматриваемый выше, должен быть только соседними безымянными детьми.Я предполагаю, что нам нужно учесть случай, когда нет неотмеченных потомков, но глубина> 0, это означает, что эта «ветвь» не достигла необходимой глубины и не может образовывать часть набора решений (поэтому весь внутренний цикл связан сэтот кортеж можно прервать).
Так будет ли это работать?Какие-нибудь серьезные недостатки?Какой-нибудь более простой / известный / канонический способ сделать это?
Одна из проблем с алгоритмом, описанным выше, заключается в том, что он не удовлетворяет требованию к эффективности памяти, так как рекурсия будет хранить в памяти большие наборы деревьев.