Графы. Реализация на языке Java обхода графа в глубину и в ширину.

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

Итак, что нам нужно? Первое, что мы сделаем – создадим структуру данных, представляющую вершину в графе. Это будет класс Vertex.

Наш класс, описывающий вершину, будет содержать всего два поля: простую текстовую метку, соответствующую вершине (это может быть просто буква или название города) и булево поле isVisited, которое нам пригодится при поиске и обозначает, была ли данная вершина посещена при обходе графа. Мы также создали несколько вспомогательных методов для получения и установки соответствующих полей.

Теперь давайте создадим класс, который будет представлять собственно сам граф.

Что нам понадобится? Мы создали несколько полей. Давайте по порядку. Поле VERTEX_MAX хранит максимально возможное количество вершин в нашем графе. Мы для примера выбрали 100. В реальных задачах их может быть гораздо больше. Массив vertexList[] необходим нам для хранения наших вершин в порядке их добавления в граф. Переменная vertexCount просто хранит число уже добавленных вершин. Ну а двумерный массив matrix есть ни что иное, как матрица смежности, описывающая наш граф.

В конструкторе класса Graph просто инициализируем все поля и заполняем матрицу смежности нулями. Что теперь? А теперь мы добавим для метода для вставки новой вершины в граф и для добавления ребра между двумя вершинами. Будем считать, что работаем с ориентированными графами. Затем вы легко сможете изменить метод для работы как с неориентированными, так и со смешанными графами, изменив буквально пару строк.

Здесь все должно быть предельно ясно. Добавляя новую вершину, мы всего лишь вставляем ее в массив и увеличиваем значение переменной vertexCount. При вставке ребра мы на пересечении наших вершин в матрице смежности ставим единицу и ноль в обратном направлении.

Обход в ширину.

Для реализации обхода в ширину нам понадобится очередь. Ее реализацию вы можете найти в одном из предыдущих уроков. В конструкторе создадим экземпляр класса JQueue.

Далее перейдем к реализации метода bfs() или обхода в ширину. В ходе выполнения обхода в ширину выполняется поиск всех преемников текущей вершины и только после этого поиск опускается на уровень ниже. Вершина, смежная с текущей вершиной, добавляется в конец очереди. Если смежных вершин больше не осталось, то текущая вершина удалятся из очереди.

Обход начинается с некоторой вершины v, мы помечаем ее как посещенную и добавляем в очередь. Далее, пока наша очередь не опустеет, мы ищем смежные непосещенные вершины. Если такая вершина есть, то она добавляется в конец очереди. Если у текущей вершины больше нет вершин-преемников, то она удаляется из очереди. В конце необходимо сбросить флаги у всех вершин для возможности повторного использования метода.

Код метода getSuccessor() для поиска смежной, непосещенной вершины приведен ниже.

Теперь вы можете протестировать правильность выполнения алгоритма. В методе main() вашего приложения создайте экземпляр класса Graph, добавьте вершины и ребра между ними и запустите метод bfs().

Обход в глубину.

Отличия в реализации этих двух методов невелики. Если в алгоритме обхода в ширину мы использовали очередь, то в методе обхода в глубину воспользуемся стеком. Инициализируем стек и реализуем обход в глубину.

Обход также начинается с некоторой вершины v. Но теперь мы не проверяем всех преемников текущей вершины, находящихся на одном уровне, а продвигаемся вглубь графа, пока по ходу продвижения по данной ветке еще находятся дочерние вершины. Если смежных вершин больше нет, то последняя последняя посещенная вершина извлекается из стека. В конце мы точно также сбрасываем все флаги, чтобы наш метод можно было использовать повторно.

Для тестирования алгоритмов создайте граф, добавьте в него вершины и ребра и проследите по своему примеру графа за выполнением алгоритма. Это даст вам более глубокое понимание самих методов. Удачи в исследованиях! До встречи в следующих статьях, в том числе по теории графов!

комментарий

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *