Какое совпадение; это тема моего блога в этот понедельник. Смотрите это для более подробной информации. А пока вот код, который поможет вам понять, как это сделать:
static IEnumerable<T> Traversal<T>(
T item,
Func<T, IEnumerable<T>> children)
{
var seen = new HashSet<T>();
var stack = new Stack<T>();
seen.Add(item);
stack.Push(item);
yield return item;
while(stack.Count > 0)
{
T current = stack.Pop();
foreach(T newItem in children(current))
{
if (!seen.Contains(newItem))
{
seen.Add(newItem);
stack.Push(newItem);
yield return newItem;
}
}
}
}
Метод принимает две вещи: элемент и отношение, которое создает множество всего, что находится рядом с элементом. Он производит обход в глубину транзитивного и рефлексивного замыкания отношения смежности на элементе . Пусть количество элементов в графе равно n, а максимальная глубина равна 1 <= d <= n, при условии, что коэффициент ветвления не ограничен. Этот алгоритм использует явный стек, а не рекурсию, потому что (1) рекурсия в этом случае превращает то, что должно быть алгоритмом O (n), в O (nd), который затем находится между O (n) и O (n ^ 2), и (2) чрезмерная рекурсия может взорвать стек, если d превышает несколько сотен узлов. </p>
Обратите внимание, что пиковое использование памяти этим алгоритмом, конечно, O (n + d) = O (n).
Так, например:
foreach(Node node in Traversal(myGraph.Root, n => n.Children))
Console.WriteLine(node.Name);
Имеет смысл?