Перечисление всех путей в дереве - PullRequest
Новая
       39

Перечисление всех путей в дереве

1 голос
/ 01 мая 2011

я пробовал и пробовал; искал и искал, но не смог найти алгоритм для решения моей проблемы. Я хочу перечислить все пути в дереве (не только простые пути), которые начинаются и заканчиваются конечными узлами (хотя это и простое ограничение).

Например, для дерева; 

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

Я хочу иметь возможность генерировать следующие пути: 

4
4-2-5
4-2-5-2-1-3-6
4-2-5-2-1-3-7
4-2-5-2-1-3-6-3-7
4-2-1-3-6
4-2-1-3-7
4-2-1-3-6-3-7
5
5-2-1-3-6
5-2-1-3-7
5-2-1-3-6-3-7
6
6-3-7
7

Полагаю, это все.

Я пробовал следующее решение Сложность поиска всех простых путей с использованием поиска в глубину? . Однако это позволяет найти только простые пути, поэтому пути, такие как 4-2-5-2-1-3-6, не могут быть найдены.

Есть ли какие-нибудь способы, которыми вы можете руководствоваться мной, любой алгоритм, возможно?

Ответы [ 2 ]

0 голосов
/ 01 мая 2011

Если ваше дерево является бинарным, вот довольно простой рекурсивный алгоритм.В Python: 

def lchild(u):
    return 2 * u

def rchild(u):
    return 2 * u + 1

def paths(u, depth):
    if depth <= 0:
        yield ((), (u,), ())
    else:
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            yield ((u,) + ldown, lpath, lup + (u,))
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            for rdown, rpath, rup in paths(rchild(u), depth - 1):
                yield ((u,) + ldown, lpath + lup + (u,) + rdown + rpath, rup + (u,))
        for rdown, rpath, rup in paths(rchild(u), depth - 1):
            yield ((u,) + rdown, rpath, rup + (u,))

if __name__ == '__main__':
    for down, path, up in paths(1, 2):
        print path
0 голосов
/ 01 мая 2011

Учитываются ли пути типа 4-2-1-2-5?Если так, то я думаю, что у меня есть ответ:

Мне кажется, что вы хотите, чтобы каждый край был посещен "один раз".Поэтому возьмите «дуал» своего графа и смотрите на пути как на последовательность ребер, а не на последовательность вершин.Таким образом, ребра становятся вашими "вершинами", а вершины становятся "ребрами" .

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

traverse(path, edg):
    mark edg as visited
    print path
    for each edge (e2) sharing a vertex with edg:
        traverse(e2, path+e2)

(with some sort of precaution to avoid duplicate paths being printed)
...