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

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

Вот мой код (кроме моего конструктора, обратите внимание, что классы 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;
}
28
задан TylerH 20 September 2019 в 19:26
поделиться

1 ответ

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

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

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

55
ответ дан 28 November 2019 в 02:58
поделиться
Другие вопросы по тегам:

Похожие вопросы: