Поиск все возможных прадеревьев

Предлагаю пойти от обратного: Получаем список всех возможных решений, затем производим валидацию каждого решения.

pdata=[
'ab',
'ad',
'bd',
'bc',
'cb',
'cd',
'dc',
]

import itertools
arr=itertools.permutations(pdata, 3)#perhaps combinations
res=[]
for it in arr:
    #filter a of valid end points 
    lst=''
    b=False
    for ita in it:
        if ita[-1] in lst:
            b=True
        else:
            lst+=ita[-1]
    if b:
        continue

    #filter b of backloop
    if 'cd' in it and 'dc' in it:
        continue
    if 'cb' in it and 'bc' in it:
        continue

    #filter c of start point
    if it[0][0]!='a':
        continue

    #filter ... 

    # filter z of unique ways
    if sorted(it) not in res:
        res.append(sorted(it)) #unique way

from pprint import pprint
pprint(res)
'''
[['ab', 'ad', 'bc'],
 ['ab', 'ad', 'dc'],
 ['ab', 'bc', 'bd'],
 ['ab', 'bd', 'dc'],
 ['ab', 'bc', 'cd'],
 ['ad', 'cb', 'dc']]
Для продолжения нажмите любую клавишу . . .
'''

Хоть пример и выполняется верно для текущей задачи, стоит заметить что ему нужны дополнительные фильтры, как то контроль взаимосвязаности (те чтобы в более сложных схемах не было двух не связаных путей), контроль вторичных точек входа (то есть чтобы входноая точка не была лишь двояко проходомой точкой), возможны и иные фильтры, описать которые не предвидится возможным из-за отсутствия полного текста задачи.

Заметим, что для каждого узла дерева (кроме корня), имеется одно (и только одно) входящее ребро. Поэтому, если в графе есть узел без входящих - то это и есть корень. Если таких узлов несколько - то решения нет. Если таких узлов нет - то корнем может быть любой узел.

Фактически, нам нужно декартово произведение множеств (списков входящих ребер), для всех вершин, кроме корня.

import itertools
from pprint import pprint

def parse_graph(graph_eidges_list):
    nodes = []
    income = {}
    outcome = {}

    for i,j in graph_eidges_list:
        outcome [i]  = outcome.get(i, []) + [j]
        income [j] = income.get(j, []) + [i]
        if not i in nodes :
            nodes += [i]
        if not j in nodes :
            nodes += [j]

    return (nodes, income, outcome)

def is_tree(graph_eidges_list, root):
    nodes, income, outcome = parse_graph(graph_eidges_list)
    if sum( [ len(j) for j in outcome.values() ] )!=len(nodes) -1 :
        return False

    def visit_outcome(r, visited):
        if r in visited:
            return False;
        visited += [r]
        if r in outcome:
            for j in outcome[r]:
                if not visit_outcome(j, visited):
                    return False
        return True

    visited = []
    if not visit_outcome(root, visited):
        return False
    return sorted(visited)==sorted(nodes)


def seek_subtree(graph_eidges_list):
    nodes, income, outcome = parse_graph(graph_eidges_list)
    result = []

    possible_roots = [ i for i in nodes if not i in income ]
    if len(possible_roots) >1 :
        return [] # no solutions.
    if len(possible_roots) ==0 :
        possible_roots = [i for i in nodes]

    for root in possible_roots:
        non_root_nodex = [ i for i in nodes if i!=root ]
        for inc in itertools.product( *[ income[i] for i in non_root_nodex ] ):
            subtree = []
            for i,j in zip(inc , non_root_nodex):
                subtree += [i+j]

            if is_tree(subtree, root):
                result += [subtree]

    return result


if __name__ == '__main__':
    pprint( seek_subtree([ 'ab', 'ad', 'bd', 'bc', 'cb', 'cd', 'dc' ] ) )

Если потребуется еще большая оптимизация, можно заменить внешнею процедуру вычисления декартова произведения, на рекурсивную процедуру, добавляющею граф на еще одно ребро. Это позволит не перебирать все варианты, отсекая случаи, когда цикл образуется уже первые добавленные ребра образуют цикл. Соответственно, выгодно перебирать вершины (при добавлении ребер), от вершин и минимальным числом входящих ребер, к вершинам с максимальным.

def clusters_join(clusters, a, b ):
    clustter_a = [ i for i in clusters if a in i ][0]
    clustter_b = [ i for i in clusters if b in i ][0]
    if clustter_a != clustter_b :
        return [ i for i in clusters if (a not in i) and (b not in i) ] + [ clustter_a + clustter_b ]
    else:
        return [i for i in clusters]

def clusters_check(clusters, a, b ):
    for i in clusters :
        if a in i :
            return not (b in i)
    return False

def seek_subtree_v2(graph_eidges_list):
    nodes, income, outcome = parse_graph(graph_eidges_list)
    result = []

    possible_roots = [ i for i in nodes if not i in income ]
    if len(possible_roots) >1 :
        return [] # no solutions.
    if len(possible_roots) ==0 :
        possible_roots = [i for i in nodes]

    for root in possible_roots:
        non_root_nodex = [ i for i in nodes if i!=root ]
        non_root_nodex = sorted( non_root_nodex, key = lambda i : len(income[i]) )

        clusters = nodes.copy()

        def visit_left_node( left_nodes, clusters, eidges ):
            if len(left_nodes) == 0 :
                if is_tree(eidges, root):
                    return [ eidges ]
            else:
                b = left_nodes[0]
                result = []
                for a in income[b]:
                    if clusters_check(clusters, a, b):
                        result += visit_left_node( left_nodes[1:], clusters_join(clusters, a,b),  eidges+[a+b],  )
                return result

        result  = visit_left_node( non_root_nodex, nodes, []  )

    return result

В работе, из которой Вы привели пример, далее рассматривается построение частичных неориентированных деревьев. Это не что иное, как остовные деревья. Поэтому первая мысль которая приходит в голову, это построить все остовные деревья, а после проверить их на «проходимость» в исходном графе.

Есть алгоритмы поиска остовных деревьев, в том числе в оптимизационных задачах. Например, MST (поиск минимального остовного дерева), и его модификации для поиска n минимальных остовных деревьев. Полагая, что веса ребер единичны, можно применить эти алгоритмы.

Также я пытался модифицировать DFS для решения этой задачи, но стабильного результата получить не удалось, поэтому пока не делюсь решением.

Но одна из моих попыток, как мне кажется. заслуживает внимания.
Имеем граф из Вашего примера:

Я разделил дуги на группы (раскрасил в разные цвета) по признаку вхождения в вершину. Главная особенность этих групп в том, что только одно ребро из группы может оказаться в прадереве. Таким образом, если мы сочетаем все группы между собой, то получим множество комбинаций дуг, подмножеством которого будут и искомые нами прадеревья. Если мы имеем m групп с количеством элементов ni в каждом, то перемножив все ni получим количество возможных комбинаций.
Для нашего графа будет три группы:

const graphGroups = [
    ['AB', 'CB'],
    ['DC', 'BC'],
    ['AD', 'BD', 'CD'],
];

Получить их очень просто из матрицы смежности, где каждый столбец и представляет собой эту группу, минуя первый, т.к. вершина A – это корень.
Сочетая эти группы получим 12 комбинаций:

Шесть из них, как видно, и есть то, что нам надо. В набор попали варианты с кратными рёбрами (6, 7, 8, 9, 12) и такие, которые не проходят через все вершины (11), а прадерево должно затронуть все N вершин графа и иметь N - 1 ребро. Их нужно исключить.

Т.е. следующая задача – это сделать тест «связности» и отфильтровать лишнее, тогда получим то, что заслуживаем:

Проверим для такого графа:

Отфильтровав 16 вариантов, получим результат:

Код на JS:

const adjMatrix = [
  [0, 1, 0, 0, 1, 0],
  [0, 0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0, 1],
  [0, 0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0, 0],
  [0, 0, 0, 0, 0, 0]
];

let graphGroups = [];
let N = adjMatrix.length;

const getLetter = i => String.fromCharCode(65 + i);

// Группируем рёбра
for (let j = 1; j < N; j++) {
  let group = [];

  for (let i = 0; i < N; i++)
    if (adjMatrix[i][j] > 0) group.push(getLetter(i) + getLetter(j));

  if (group.length > 0) graphGroups.push(group);
}

const reverseStr = (s) => s.split('').reverse().join('');

// Тест дерева
const testTree = (edges, size) => {
  let testTable = {};

  let checkPointsCount = [...new Set(edges.join(''))].join('').length == size;
  let checkDoubleEdges = edges.every((v) => {
    return testTable.hasOwnProperty(reverseStr(v)) ?
      false :
      testTable[v] = true;
  });

  return checkPointsCount && checkDoubleEdges;
}

// Формируем деревья

let queue = [graphGroups[0]];
let row = Array(graphGroups.length).fill('');
let i = 0;
let size = graphGroups.length;
let out = [];

while (i >= 0) {
  if (queue[i].length == 0) {
    i--;
    queue.pop();
  } else {

    row[i] = queue[i].shift();

    if (i < size - 1)
      queue.push(graphGroups[++i].slice());
    else if (testTree(row, N))
      out.push(row.slice());
  }
};


// Вывод
graphPoints = {
  A: [0, 40],
  B: [40, 0],
  C: [40, -40],
  D: [-40, -40],
  E: [-40, 0],
  F: [0, -20],
};

out.every((v, i) => makeGraphTree(graphPoints, v, '' + (i + 1)));
console.log(out);



// Вспомогалки-рисовалки
function makeGraphTree(points, edges, text = '5') {
  var canvas = document.createElement("canvas");
  var ctx = canvas.getContext("2d");

  canvas.width = 100;
  canvas.height = 100;

  ctx.translate(50, 50);
  if (text.length > 0) ctx.fillText(text, -45, -37);
  ctx.scale(1, -1);
  ctx.lineWidth = 0.5;

  ctx.fillStyle = 'red';

  Object.entries(points).map(p => drawDot(ctx, p[1]));

  ctx.beginPath();
  edges.map((e) => drawArrow(ctx, points[e[0]], points[e[1]]));
  ctx.stroke();

  document.body.appendChild(canvas);
  return true;
}

function drawDot(ctx, p) {
  ctx.beginPath();
  ctx.arc(p[0], p[1], 3, 0, 2 * Math.PI, false);
  ctx.fill();
}

function drawArrow(ctx, p1, p2) {
  var headSize = 10;
  var dx = p2[0] - p1[0];
  var dy = p2[1] - p1[1];
  var angle = Math.atan2(dy, dx);
  ctx.moveTo(p1[0], p1[1]);
  ctx.lineTo(p2[0], p2[1]);
  ctx.lineTo(p2[0] - headSize * Math.cos(angle - Math.PI / 8), p2[1] - headSize * Math.sin(angle - Math.PI / 8));
  ctx.moveTo(p2[0], p2[1]);
  ctx.lineTo(p2[0] - headSize * Math.cos(angle + Math.PI / 8), p2[1] - headSize * Math.sin(angle + Math.PI / 8));
}

Сразу скажу, я не проверял на всех возможных графах и пока не уверен, что тест на кратность и прохождение всех точек является исчерпывающим. Также для правильного представления и обхода дерева, надо отсортировать полученные наборы ребер.