WedX - журнал о программировании и компьютерных науках

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

Я хочу создать поиск в глубину, в котором я несколько преуспел.

Вот мой код на данный момент (за исключением моего конструктора, обратите внимание, что классы Vertex и Edge содержат только свойства, здесь нет ничего важного):

private Stack<Vertex> workerStack = new Stack<Vertex>();
private List<Vertex> vertices = new List<Vertex>();
private List<Edge> edges = new List<Edge>();

private int numberOfVertices;
private int numberOfClosedVertices;
private int visitNumber = 1;

private void StartSearch()
{
    // Make sure to visit all vertices
    while (numberOfClosedVertices < numberOfVertices && workerStack.Count > 0)
    {
        // Get top element in stack and mark it as visited
        Vertex workingVertex = workerStack.Pop();
        workingVertex.State = State.Visited;

        workingVertex.VisitNumber = visitNumber;
        visitNumber++;

        numberOfClosedVertices++;

        // Get all edges connected to the working vertex
        foreach (Vertex vertex in GetConnectedVertices(workingVertex))
        {
            vertex.Parent = workingVertex;
            workerStack.Push(vertex);
        }
    }
}

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> vertices = new List<Vertex>();

    // Get all vertices connected to vertex and is unvisited, then add them to the vertices list
    edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

    return vertices;
}

Это работает так, что все вершины посещаются, но не в правильном порядке.

Вот сравнение того, как меня посещают, по сравнению с википедией: Comparison

Кажется, шахта перевернута и идет справа налево.

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

РЕДАКТИРОВАТЬ: я получил свой ответ, но все же хотел показать конечный результат для метода GetConnectedVertices:

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> connectingVertices = new List<Vertex>();

    (from edge in edges
     where edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited
     select edge).
     Reverse().
     ToList().
     ForEach(edge => connectingVertices.Add(edge.VertexTarget));

    return connectingVertices;
}
27.04.2011

Ответы:


1

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

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

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

27.04.2011
  • Да, это намного лучше. Только один вопрос: рекомендуете ли вы, чтобы мой класс Vertex содержал ребра, связанные с вершиной, чтобы метод GetNeighbours использовал эти ребра для поиска своих соседей? Кстати, я все же пометил ответ Адриана как принятый ответ, так как он решил мою первоначальную проблему (хотя я поставил вам большой палец вверх :-)) 28.04.2011
  • @Dumpen: это зависит от характера графика. Предположим, что V и E — количество вершин и ребер. Если коэффициент ветвления E/V, то есть среднее число ребер на вершину, низкий, ваше предложение эффективно. Если оно велико (поскольку каждая вершина связана почти с каждой вершиной), тогда неэффективно хранить всю эту информацию для каждой вершины; вместо этого создайте двумерную граничную таблицу логических значений и поддерживайте ее в графе. 28.04.2011
  • Хорошо, еще раз спасибо. У меня работает ваш код, но последний вопрос (надеюсь): почему вы объявляете хеш-набор и стек с помощью var вместо того, чтобы сообщить компилятору, что такое тип данных? 28.04.2011
  • @Dumpen: компилятору не нужна моя помощь; он знает, что такое тип данных. Вопрос о том, использовать ли var в этом случае, заключается в том, нужна ли людям помощь, чтобы понять это. Вы человек; вам действительно нужно увидеть Stack‹Vertext› stack = new Stack‹Vertex›(), чтобы понять, что стек — это стек вершин? Я сомневаюсь в этом. Избыточность усложняет чтение кода, а не упрощает его, поэтому устраните его. Дополнительные мысли по этому вопросу см. в разделе blogs.msdn.com/b/ericlippert/archive/2011/04/20/ 28.04.2011
  • Для получения дополнительной информации о вашем вопросе о том, как представлять графики, см. en.wikipedia.org/wiki/ Graph_(data_structure) -- вы предлагаете подход со списком смежности, который хорош для разреженных графов. Подход с использованием матрицы смежности более эффективен для плотных графов. 28.04.2011
  • @EricLippert, разве это не содержит ошибку, из-за которой вершину можно посетить более одного раза, поскольку посещенный набор проверяется только при добавлении в стек (но не проверяется во время посещения), поэтому вы можете получить два повторяющихся объекта вершины в стеке сразу. Пример A-›B, A-›C, B-›C. В этом примере C может быть посещен дважды. 11.09.2013
  • @вулканворон. Баг исчез, но теперь, когда он видит посещенный узел, ему приходится заново перебирать всех соседей (глубоко) и обнаруживать, что они уже посещены. В моей реализации я просто проверяю возвращаемое значение Add и, если оно не новое, продолжаю. т.е. if (!visited.Add(current)) continue; yield return current; 20.01.2014
  • Кто-нибудь может объяснить, что означает эта строка? var neighbours = graph.GetNeighbours(current) .Where(n=>!visited.Contains(n)); Особенно .Where(n=>!visited.Contains(n)). 22.12.2017
  • @ Atlas2k: Можете ли вы задать более конкретный вопрос? Строка кода означает получение соседей, которых я еще не посетил. Мы представляем это, имея набор посещенных узлов, и мы получаем всех соседей, которых еще нет в наборе посещенных узлов. Вы спрашиваете, почему мы не хотим посещать узлы, которые уже посетили? Потому что проблема заключается в том, чтобы посетить каждый узел в глубине первого порядка. 22.12.2017
  • Мой вопрос еще более простой, чем этот. Я не знаю, что означает 'n=›', и мне было сложно найти этот набор символов в Google. Спасибо за объяснение. 22.12.2017
  • @ Atlas2k: ключевые слова, которые вы хотите найти, — это лямбда-выражение и LINQ. 23.12.2017
  • @EricLippert Последний фрагмент кода больше похож на обход в ширину, чем на обход в глубину. Разве это не обход БФ? 02.06.2018
  • @ziezi на твой вопрос легко ответить самому. Создайте граф в виде дерева и запустите алгоритм. В каком порядке он обходил узлы? 03.06.2018

  • 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);
    
    21.09.2012
  • Я думаю, что это может содержать ошибку, как я уже упоминал в своих комментариях в ответе @EricLippert. 11.09.2013

  • 3

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

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

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

    27.04.2011
  • Изменение порядка списка (использование Reverse()), похоже, решает проблему. Спасибо за ответ, направил меня в правильном направлении. 27.04.2011
  • @Dumpen: Вы можете сделать это более эффективно, чем используя Reverse. Создайте еще один стек! Таким образом, он автоматически перечисляется в обратном порядке. 27.04.2011
  • Ох уж этот тесак. Вы имеете в виду вот так? ` edge.FindAll(edge ​​=> edge.VertexSource == вершина && edge.VertexTarget.State == State.Unvisited). ForEach(edge ​​=›connectingVertices.Push(edge.VertexTarget)); ` (Извините, я не умею форматировать код) 27.04.2011

  • 4

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

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

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

    27.04.2011

    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;
        }
    
    27.04.2011
  • Спасибо. Я обязательно посмотрю на это, однако на данный момент у меня, кажется, достаточно с текущим сценарием в голове :) 27.04.2011
  • рекурсия - не всегда хорошая идея, я был бы осторожен, используя это решение. 09.11.2011

  • 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;
        }
    
    18.06.2015
    Новые материалы

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

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

    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..

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

    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..

    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..


    Для любых предложений по сайту: [email protected]