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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 комментариев

  1. Avdok Ответить

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

  2. Евгений Ответить

    Строки вида «vertexList[vertex].isVisited = true;» тоже содержат ошибку.
    В классе Vertex в начале isVisited декларирован как приватная переменная и даже setter для него есть, так что кажется должно быть вида «vertexList[vertex].setVisited(true);»

  3. Yuri Ответить

    Да простит меня автор, выкладываю докрученный рабочий пример с обходом в глубину:

    public class Vertex {

    private String label;
    private boolean isVisited;

    public Vertex(String label)
    {
    this.label = label;
    isVisited = false;
    }

    public String getLabel() {
    return label;
    }

    public void setLabel(String label) {
    this.label = label;
    }

    public boolean isVisited() {
    return isVisited;
    }

    public void setVisited(boolean isVisited) {
    this.isVisited = isVisited;
    }

    }

    ///////////////////////////////////

    public class Stack {
    private int maxSize;//Размер массива
    public final int[] stackArray;
    public int top;//Вершина стека

    public Stack(int n) {
    maxSize = n;
    stackArray = new int[maxSize];
    top = -1;
    }

    @Override
    public String toString() {
    String result = «»;
    for (int i = 0; i «;
    }
    return result.substring(0, result.length() — 3);
    }

    //поместить элемент в стек
    public void push(int node) {
    stackArray[++top] = node;//Увеличение top, вставка элемента
    }

    //Извлечение элемента с вершины стека
    public int pop() {
    return stackArray[top—];//Извлечение элемента, уменьшение top
    }

    //Чтение элемента с вершины стека
    public int peek() {
    return stackArray[top];
    }

    public boolean isEmpty() {
    //True, если стек пуст
    return (top == -1);
    }

    public boolean isFull() {
    //True, если стек полон
    return (top == maxSize — 1);
    }

    }

    ///////////////////////////////////

    public class Graph {

    //максимальное количество вершин в графе
    private int VERTEX_MAX;
    //массив для хранения вершин
    private Vertex[] vertexList;
    //текущее количество вершин в графе
    private int vertexCount;
    //матрица смежности
    private int[][] matrix;
    private Stack stack;

    public Graph(int n) {
    VERTEX_MAX = n;
    matrix = new int[VERTEX_MAX][VERTEX_MAX];
    //перед началом работы заполняем матрицу смежности нулями
    for (int i = 0; i < VERTEX_MAX; i++)
    for (int j = 0; j < VERTEX_MAX; j++)
    matrix[i][j] = 0;
    vertexCount = 0;
    vertexList = new Vertex[VERTEX_MAX];
    stack = new Stack(VERTEX_MAX);
    }

    //добавление вершины
    public void addVertex(String label) {
    vertexList[vertexCount++] = new Vertex(label);
    }

    //добавление ребра
    public void addEdge(int begin, int end) {
    matrix[begin][end] = 1;
    matrix[end][begin] = 0;
    }

    //метод возвращает непосещенную вершину, смежную по отношению к v
    int getSuccessor(int v) {
    for (int j = 0; j < vertexCount; j++)
    if (matrix[v][j] == 1 && vertexList[j].isVisited() == false)
    return j; //возвращает первую найденную вершину
    return -1; //таких вершин нет
    }

    // обход в глубину
    void dfs(int v) {
    vertexList[v].setVisited(true);//алгоритм начинает обход с вершины 0
    stack.push(v);//занесение в стек
    int i = 0;
    //выведем вершину, с которой начинается обход, на экран
    System.out.println(vertexList[v].getLabel());

    while (!stack.isEmpty()) //пока стек не опустеет
    {
    int current = stack.peek();

    //получение непосещенной вершины, смежной с текущей
    int vertex = getSuccessor(current);
    if (vertex == -1) {
    stack.pop();//элемент извлекается из стека
    } else //если вершина найдена
    {
    vertexList[vertex].setVisited(true);//пометка
    // displayVertex(vertex);//вывод
    stack.push(vertex);//занесение в стек
    String result = "";
    for (int j = 0; j «;
    }
    System.out.println(result.substring(0, result.length() — 3));
    }
    }

    //сброс флагов
    for (int j = 0; j < vertexCount; j++)//сброс флагов
    vertexList[j].setVisited(false);

    }

    public static void main(String[] args) {

    Graph graph = new Graph(6);

    graph.addVertex("A");
    graph.addVertex("B");
    graph.addVertex("C");
    graph.addVertex("D");
    graph.addVertex("E");
    graph.addVertex("F");

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(2, 5);

    for (int i = 0; i < graph.matrix.length; i++) {
    for (int j = 0; j < graph.matrix[i].length; j++) {
    System.out.print(graph.matrix[i][j] + "\t");
    }
    System.out.println();
    }

    graph.dfs(0);

    }

    }

    • Yuri Ответить

      Прошу прощения, криво вставилось сообщение. Прошу считать предыдущий комментарий недействительным.

  4. Евгений Ответить

    Автор просто тупой мудак, не тратьте время зря на прочтение этого дерьма

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

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