Пример реализации графа в Java

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

Пример представляет собой захватывающую и сложную задачу для решения. Сначала я представлю саму проблему и возможный способ ее решения на Java.

Посмотрите этот урок на Youtube

Назначение

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

Зона доставки представлена ​​в виде двумерной сетки целых чисел, где:

• 1 представляет доступную область
• 0 представляет недоступную область
• 2 представляет пункт назначения заказа

Эта задача — одно из моих любимых заданий по Java для практики. Отличный пример реализации графа на Java, показывающий, как использование правильной структуры данных может превратить, казалось бы, сложную проблему в нечто гораздо более простое.

Некоторые вещи, которые вы должны рассмотреть, прежде чем начать. Грузовик не может покинуть сетку и должен добраться до места назначения заказа через доступные зоны. И грузовик может перемещаться на одну клетку вверх, вниз, влево или вправо за раз.

Вот несколько примеров различных случаев с входами и соответствующими выходами:

  Example 1
  grid = [[1,1,0],[0,1,2][0,1,1]]
  Output: [0,0][0,1][1,1][2,1][2,2][1,2]
  
  Example 2
  grid = [[1,1,1,1],[0,1,0,1],[0,1,0,1],[0,1,1,0],[0,1,2,1]]
  Output: [0,0][0,1][1,1][2,1][3,1][3,2]

Как решить

Лучшим решением этой проблемы является использование реализации графа Java. В общем, граф — правильное решение для любой ситуации, когда нужно ориентироваться в сетке.

Кроме того, я советую вам решить эту проблему, следуя подходу, основанному на тестировании, что означает определение сигнатуры функции для выполнения вычислений без написания кода. Затем напишите несколько тестов. И последнее, написание кода. Зачем писать тесты? Будет намного проще и быстрее проверить, что все работает правильно.

В нашем решении будет два класса: класс Cell, представляющий каждую ячейку матрицы, и DeliveryArea, представляющий область, по которой должен перемещаться грузовик. См. скелет ниже, только класс и сигнатуры методов. Мы завершим реализацию в следующем разделе.

Имя файла: Cell.java

public class Cell {
    public int row;
    public int col;

    public Cell(int row, int col){
        this.row = row;
        this.col = col;
    }

    public String hashKey(){
        return String.valueOf(this.row)+String.valueOf(this.col);
    }
}

Имя файла: DeliveryArea.java

import java.util.List;
import java.util.Map;

public class DeliveryArea {

    private final static int ACCESSIBLE_CELL = 1;
    private final static int NON_ACCESSIBLE_CELL = 0;
    private final static int DESTINATION = 2;

    public int[][] matrix;

    public DeliveryArea(int[][] matrix){
        this.matrix = matrix;
    }
    private Map<String, List<Cell>> buildGraph(){
        return null;
    }
    public List<Cell> findRoute(){
        return null;
    }
}

См. готовое решение на сайте hellocodeclub.com.

Надеюсь, вам понравилась статья и спасибо за чтение! Удачного кодирования!