Кажется, моя развернута и начинается справа налево.Вы знаете, что вызывает это?
Как уже отмечали другие, вы перемещаете узлы к следующему посещению в стеке в порядке слева направо.Это означает, что они выталкиваются справа налево, так как стек меняет порядок.Стеки являются последними в первых.
Вы можете решить эту проблему, заставив GetConnectedVertices создать стек, а не список.Таким образом, связанные вершины меняются местами дважды , один раз, когда они идут в возвращенный стек, и один раз, когда они идут в реальный стек.
Также любые советы по моей реализации будутс благодарностью
Реализация работает, я полагаю, но у нее очень много фундаментальных проблем.Если бы мне представили этот код для проверки, вот что я бы сказал:
Прежде всего, предположим, что вы хотите выполнить два поиска в глубину этой структуры данных одновременно.Либо потому, что вы делали это в нескольких потоках, либо потому, что у вас есть вложенный цикл, в котором внутренний цикл выполняет DFS для элемента, отличного от внешнего цикла.Что просходит?Они мешают друг другу, потому что оба пытаются изменить поля «State» и «VisitNumber».Это действительно плохая идея - иметь то, что должно быть «чистой» операцией, такой как поиск, на самом деле делает вашу структуру данных «грязной».
Это также делает невозможным использование постоянных неизменяемых данных для представления избыточных частей вашего графика.
Кроме того, я замечаю, что вы пропускаете очищающий код.Когда «State» когда-либо возвращается к своему первоначальному значению?Что делать, если вы сделали секунду 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, то итерация прекращается, когда критерии поиска удовлетворяются. Нам не нужно делать полный обход, если мы находим результат рано.