Рекурсивное лямбда-выражение для поиска пути (ей) через ориентированный граф?

Question

Мне нужно найти путь или пути по сложной структуре графа. График построен с использованием чего-то похожего на это:

class Node
{
    public string Value { get; set;}
    public List<Node> Nodes { get; set;}

    public Node()
    {
        Nodes = new List<Node>();
    }
}

Что делает это сложным, так это то, что узлы могут ссылаться на более ранний узел. Например,

A -> C -> E -> A

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

List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);

У кого-нибудь есть способ построить это (или что-то подобное)? Я делал рекурсию в прошлом, но по какой-то причине у меня полный мозг и пердеж. В моем вопросе указано лямбда-выражение, но использование лямбда-выражения необязательно. Буду благодарен за любое решение.

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

Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root);  // where root is the tree structure

Редактировать

Основываясь на комментариях и ответах ниже, я нашел отличное решение в CodeProject. Он использует алгоритм поиска пути A *. Вот ссылка.

Answer 1

Если ваша проблема связана с поиском пути, вы можете выбрать в Google «Звезда» или «A *». Это общий и эффективный алгоритм поиска пути. См. эту статью для примера, непосредственно связанного с вашей проблемой.

Возможно, вы захотите взглянуть на алгоритм Dijsktra

Answer 2

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

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

1. Добавьте параметры для представления искомой цели, набора успешных путей и текущего пути с начала.

2. При вводе узла, соответствующего цели, добавьте текущий путь (плюс текущий узел) в список успешных путей.

3. Расширить текущий путь текущим узлом, чтобы создать путь, передаваемый при любых рекурсивных вызовах.

4. Вызовите исходный вызов ExploreGraph с пустым путем и пустым списком успешных путей.

По завершении ваш алгоритм пройдет через весь граф, и будут найдены различные пути к цели.

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

Answer 3

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

Пример:

  public void ExploreGraph(TreeNode tn, Dictionary<TreeNode, bool> visitednodes)
        {

            foreach (Treenode childnode in tn.Nodes)
            {
                if (!visitedNodes.ContainsKey(childnode))
                {
                    visitednodes.Add(childnode);
                    ExploreGraph(childnode, visitednodes);
                }
            }
        }