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

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 "звездочку" или "А *".Это распространенный и эффективный алгоритм поиска пути.Видишь эта статья приведу пример, непосредственно связанный с вашей проблемой.

Возможно, вы также захотите взглянуть на Алгоритм Дейсктры

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);
                }
            }
        }