[Грокаем алгоритмы] Алгоритм поиска в ширину на C# (BFS)

Всем читающим эту статью здрасте. Сегодня я хотел бы поделиться с вами своей реализацией поиска в ширину (BFS) на C#.

Негативные комментарии, касающиеся моего говнокода и реализации поддерживаются. Настоятельно рекомендую вам высказаться по поводу всего. Я начинающий, поэтому думаю, что это даже к лучшему.

Для начала я хотел бы кратко ознакомить вас с принципом работы моего кода

Что к чему?

Итак, изначально я создал класс под названием BFS:

class BFS{    }

Далее я начал создавать такие поля и свойства, как:

• Начальное значение (StartValue)

• Конечное значение (GoalValue)

• Словарь с вершинами (Graph)

• Очередь (Queue)

• И проверенные значения (UsedValues)

class BFS     {         private string _startValue;         public string StartValue {              get { return _startValue; }              set { _startValue = value; }         }          private string _goalValue;         public string GoalValue         {             get { return _goalValue; }             set { _goalValue = value; }         }          private Dictionary<string, string[]> _graph = new Dictionary<string, string[]>();         public Dictionary<string, string[]> Graph         {             get { return _graph; }             set { _graph = value; }         }          private Queue<string> _queue = new Queue<string>();         public Queue<string> Queue         {             get { return _queue; }             set { _queue = value; }         }          private List<string> _usedValues = new List<string>();         public List<string> UsedValues         {             get { return _usedValues; }             set { _usedValues = value; }         } }

Объявил конструктор класса:

public BFS(string startValue, string goalValue, Dictionary<string, string[]> graph) {   StartValue = startValue;   GoalValue = goalValue;   Graph = graph; }

Создал метод поиска кратчайшего пути:

public void Search() {   Queue.Enqueue(StartValue);    while (Queue.Count != 0)   {     string node = Queue.Dequeue();     string[] vertites = Graph[node];      if (node == GoalValue)     {       return;     }      foreach (string vertite in vertites)     {       if (!UsedValues.Contains(vertite))       {         if (vertite == GoalValue)         {           if (Queue.Count > 0)           {             Queue.Dequeue();           }           Queue.Enqueue(node);           Queue.Enqueue(GoalValue);           return;         }         Queue.Enqueue(vertite);        }      }     UsedValues.Add(node);   } }

И, наконец, метод вывода кратчайшего пути:

public void ShortestWay() {     Search();      Console.Write($"{StartValue} ");     foreach (string value in Queue)     {       Console.Write($"--> {value} ");     } }

Работа программы

За основу возьмем вот такой вот граф:

Кратчайший путь от A до B равен А -> P -> B

Запускаем программу, и получаем такой же вывод

Заключение

На этом в принципе можно и заканчивать. Кто дочитал до конца, тому я сильно благодарен. Поддерживаю критику в сторону моего кода, приму все во внимание

Кто хочет скачать код, держите ссылку на GitHub.