Внедрение глубины Первый поиск в С# с использованием списка и стека

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

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

Затем вы изменяете свойство "parent", но совершенно неясно, для чего это свойство или почему оно мутируется во время обхода. Вершины в произвольном графе не имеют "родителей", если граф не является деревом, а если граф является деревом, то нет необходимости отслеживать состояние "посещенных"; в дереве нет петель. Что здесь происходит? Этот код просто причудливый, и нет необходимости выполнять 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, то итерация прекращается, когда выполняются критерии поиска. Нам не нужно делать полный обход, если мы рано найдем результат.

Ответ 2

Я обобщил код @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);

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

Вам может понравиться следующее:

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

Ответ 6

Это моя реализация, один стек достаточно хорош. Реверс делается перед циклом 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;
    }