Реализация поиска в глубину на C# с использованием списка и стека

Кажется, моя перевернута и начинается справа налево. Вы знаете, что вызывает это?

Как уже отмечали другие, вы нажимаете узлы для посещения в стеке в порядке слева направо. Это означает, что они выталкиваются справа налево, поскольку стек имеет обратный порядок. Стеки действуют в порядке поступления.

Вы можете решить эту проблему, заставив GetConnectedVertices создавать стек, а не список. Таким образом, соединенные вершины переворачиваются дважды: один раз, когда они попадают в возвращаемый стек, и один раз, когда они попадают в реальный стек.

Также буду очень признателен за любые советы по моей реализации

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

Во-первых, предположим, что вы хотите выполнить два поиска в глубину этой структуры данных одновременно. Либо потому, что вы делали это в нескольких потоках, либо потому, что у вас есть вложенный цикл, в котором внутренний цикл выполняет DFS для другого элемента, чем внешний цикл. Что просходит? Они мешают друг другу, потому что оба пытаются изменить поля "State" и "VisitNumber". Это действительно плохая идея иметь то, что должно быть «чистой» операцией, такой как поиск, на самом деле делает вашу структуру данных «грязной».

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

Кроме того, я заметил, что вы опускаете очищающий код. Когда «Состояние» когда-либо возвращалось к исходному значению? Что, если вы выполнили вторую DFS? Это немедленно потерпит неудачу, так как корень уже посещен.

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

Далее, почему все объекты состояния являются частными переменными класса? Это простой алгоритм; нет необходимости создавать для него целый класс. Алгоритм поиска в глубину должен использовать граф для поиска как формальный параметр, а не как состояние объекта, и он должен поддерживать свое собственное локальное состояние по мере необходимости в локальных переменных, а не в полях.

Далее, абстракция графа... ну, это не абстракция. Это два списка, один из вершин и один из ребер. Откуда мы знаем, что эти два списка хотя бы непротиворечивы? Предположим, что есть вершины, которых нет в списке вершин, но которые есть в списке ребер. Как это предотвратить? Вам нужна абстракция графа. Пусть реализация абстракции графа заботится о том, как представлять ребра и находить соседей.

Далее, ваше использование ForEach является и законным, и обычным, но это вызывает у меня головную боль. Трудно читать ваш код и рассуждать об этом со всеми лямбда-выражениями. У нас есть прекрасное выражение foreach. Используй это.

Затем вы изменяете «родительское» свойство, но совершенно не ясно, для чего это свойство или почему оно изменяется во время обхода. Вершины в произвольном графе не имеют «родителей», если граф не является деревом, а если граф является деревом, то нет необходимости отслеживать «посещенное» состояние; в дереве нет петель. Что здесь происходит? Этот код просто странный, и нет необходимости выполнять DFS.

Далее, ваш вспомогательный метод с именем GetConnectedVertices является ложью. Он не получает связанные вершины, он получает связанные еще не посещенные вершины. Методы, названия которых лгут, очень сбивают с толку.

Наконец, заявлено, что это поиск в глубину, но он ничего не ищет! Где искомая вещь? Куда возвращается результат? Это вообще не поиск, это обход.

Начать сначала. Что ты хочешь? Обход графа в глубину с заданной начальной вершиной. Затем реализуйте это. Начните с определения того, что вы пересекаете. График. Какая услуга вам нужна от графа? Способ получения множества соседних вершин:

interface IGraph
{
    IEnumerable<Vertex> GetNeighbours(Vertex v);
}

Что возвращает ваш метод? Последовательность вершин в порядке глубины. Что для этого потребуется? Начальная вершина. OK:

static class Extensions
{
    public static IEnumerable<Vertex> DepthFirstTraversal(
        this IGraph graph, 
        Vertex start) 
    { ... }
}

Теперь у нас есть тривиальная реализация поиска в глубину; теперь вы можете использовать предложение Where:

IGraph myGraph = whatever;
Vertex start = whatever;
Vertex result = myGraph.DepthFirstTraversal(start)
                       .Where(v=>something)
                       .FirstOrDefault();

Итак, как мы собираемся реализовать этот метод, чтобы он выполнял обход, не разрушая состояние графа? Поддерживайте собственное внешнее состояние:

public static IEnumerable<Vertex> DepthFirstTraversal(
    this IGraph graph, 
    Vertex start) 
{
    var visited = new HashSet<Vertex>();
    var stack = new Stack<Vertex>();

    stack.Push(start);

    while(stack.Count != 0)
    {
        var current = stack.Pop();

        if(!visited.Add(current))
            continue;

        yield return current;

        var neighbours = graph.GetNeighbours(current)
                              .Where(n=>!visited.Contains(n));

        // If you don't care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse()) 
            stack.Push(neighbour);
    }
}

Видите, насколько это чище и короче? Отсутствие мутации состояния. Никаких возни со списками краев. Нет плохо названных вспомогательных функций. И код на самом деле делает то, о чем говорит: обходит граф.

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

Я обобщил код @Eric для обхода DFS для любого T, чтобы все работало для любого типа, у которого есть дочерние элементы, - я подумал, что поделюсь:

public static IEnumerable<T> DepthFirstTraversal<T>(
    T start,
    Func<T, IEnumerable<T>> getNeighbours)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(start);

    while (stack.Count != 0)
    {
        var current = stack.Pop();

        if (!visited.Add(current))
            continue;

        yield return current;

        var neighbours = getNeighbours(current).Where(node => !visited.Contains(node));

        // If you don't care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse())
        {
            stack.Push(neighbour);
        }
    }
}

Пример использования:

var nodes = DepthFirstTraversal(myNode, n => n.Neighbours);

Проблема в порядке поиска элементов. Ваш for each в StartSearch не гарантирует порядок элементов. Как и вы FindAll в GetConnectedVertices методе. Давайте посмотрим на эту строку:

edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

Вы должны добавить OrderBy(), чтобы обеспечить желаемый порядок.

Элементы будут извлекаться из стека в порядке, обратном тому, как они помещаются в него:

stach.push() приводит к: 1 2 3 4 5

stack.pop() приводит к: 5 4 3 2 1 (итак: справа налево)

Вам может понравиться это:

        public static bool DepthFirstSearch<T>(this IEnumerable<T> vertices, T rootVertex, T targetVertex, Func<T, IEnumerable<T>> getConnectedVertices, Func<T, T, bool> matchFunction = null)
    {
        if (getConnectedVertices == null)
        {
            throw new ArgumentNullException("getConnectedVertices");
        }
        if (matchFunction == null)
        {
            matchFunction = (t, u) => object.Equals(t, u);
        }
        var directlyConnectedVertices = getConnectedVertices(rootVertex);
        foreach (var vertex in directlyConnectedVertices)
        {
            if (matchFunction(vertex, targetVertex))
            {
                return true;
            }
            else if (vertices.DepthFirstSearch(vertex, targetVertex, getConnectedVertices, matchFunction))
            {
                return true;
            }
        }
        return false;
    }

Это моя реализация, одного стека достаточно. Обратное выполняется перед циклом foreach.

    /// <summary>
    /// Depth first search implementation in c#
    /// </summary>
    /// <typeparam name="T">Type of tree structure item</typeparam>
    /// <typeparam name="TChilds">Type of childs collection</typeparam>
    /// <param name="node">Starting node to search</param>
    /// <param name="ChildsProperty">Property to return child node</param>
    /// <param name="Match">Predicate for matching</param>
    /// <returns>The instance of matched result, null if not found</returns>
    public static T DepthFirstSearch<T, TChilds>(this T node, Func<T, TChilds> ChildsProperty, Predicate<T> Match) 
        where T:class
    {
        if (!(ChildsProperty(node) is IEnumerable<T>))
            throw new ArgumentException("ChildsProperty must be IEnumerable<T>");

        Stack<T> stack = new Stack<T>();
        stack.Push(node);
        while (stack.Count > 0) {
            T thisNode = stack.Pop();
            #if DEBUG
            System.Diagnostics.Debug.WriteLine(thisNode.ToString());
            #endif
            if (Match(thisNode))
                return thisNode;
            if (ChildsProperty(thisNode) != null) {
                foreach (T child in (ChildsProperty(thisNode) as IEnumerable<T>).Reverse()) 
                    stack.Push(child);
            }
        }
        return null;
    }