C#. Поиск путей в орграфах методом DepthFirstSearch

Git

Возьмем за основу алгоритм DFS для орграфов. И напишем поиск путей из одной вершины в другую. Конечный вариант будет выглядеть примерно так…

Напишем небольшой класс для поиска путей, он будет выглядеть примерно так…

Самый главный метод тут Dfs. Что мы делаем? Отмечаем вершину, проходим по смежным вершинам и отмечаем ориентированные ребра в специальном массиве, который позже позволит построить нам путь в методе GetPathTo. Мы как бы разматываем клубок с конца. И складываем вершины пути в стэк, получая необходимый путь.

Используя этот класс, допишем в классе Digraph следующие методы

Класс Digraph полностью

Класс Bag

Пример применения

 

 

This entry was posted in C#. Bookmark the permalink.

Leave a Reply