Перечислять граф рекурсивно - PullRequest
Новая
       27

Перечислять граф рекурсивно

2 голосов
/ 05 февраля 2012

У меня есть следующие (конкретные): 

public interface IDirectory
{
   IEnumerable<IDirectory> Directories{get;}
}

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

Ответы [ 3 ]

9 голосов
/ 06 февраля 2012

Два других решения являются типичными рекурсивными решениями этой проблемы и подходят для мелких графов без циклов.Если у вас есть глубокий график с циклами, они не будут работать хорошо.Вам будет лучше с чем-то вроде этого: 

public static IEnumerable<T> DepthFirstTraversal<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var set = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count != 0)
    {
        T current = stack.Pop();
        if (set.Contains(current)) continue;
        yield return current;
        set.Add(current);
        foreach(var child in children(current))
            stack.Push(child);
    }
}

, а затем вызывать его с 

foreach(var d in DepthFirstTraversal(root, x=>x.Directories))
   ...

. Набор отслеживает уже посещенные узлы и поэтому занимает O (n) пространство.Нет рекурсии, поэтому это O (1) в пространстве стека.

Если вы знаете, что циклов нет, вы можете исключить набор и сэкономить на этой стоимости.

4 голосов
/ 06 февраля 2012

Укороченная версия: 

IEnumerable<IDirectory> Enumerate(IDirectory parent)
{
    return new[] { parent }.Concat(parent.Directories.SelectMany(Enumerate));
}

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

4 голосов
/ 05 февраля 2012 
IEnumerable<IDirectory> Enumerate(IDirectory parent)
{
    yield return parent;
    foreach (var child in parent.Directories)
        foreach (var directory in Enumerate(child))
            yield return directory;
}

Не самый эффективный, но работает.Эрик Липперт написал несколько статей о том, как вы могли бы сделать это более эффективно (но менее кратко), используя Stack<IDirectory> вместо рекурсивных вызовов методов.

...