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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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, то итерация прекращается, когда критерии поиска удовлетворяются. Нам не нужно делать полный обход, если мы находим результат рано.