Graph Implementation Example in Java

In this article you will see a graph implementation example in Java from scratch. You will learn how to create and use a graph data structure in Java, practicing with a real exercise that I have seen in many interview processes.

The example is an exciting and challenging problem to solve. Firstly I will introduce the problem itself and a possible way to solve it in Java.

The problem

A delivery service company creates a system that will plan a route for a delivery truck to deliver customer orders. The planner will create a delivery area for each order, which is abstracted as a grid. The challenge is to write an algorithm to find a path for the truck to deliver the order.

The delivery area is represented as a two-dimensional grid of integers where:

• 1 represents an accessible area
• 0 represents a non-accessible area
• 2 represents the order destination

This exercise is an excellent example in Java of how using the correct data structure can turn a seemingly complex problem into something much more straightforward. The problem becomes simpler when you use a graph implementation.

Some stuff you should consider before starting. The truck can’t leave the grid and should get to the order destination through the accessible areas. And the truck can move one cell up, down, left, or right at a time.

Here are some examples of different cases with the inputs and the corresponding outputs:

  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]

Solution

The best solution to this problem is using a java graph implementation. In general, a graph is the right solution for any situation where you need to navigate a grid.

This solution will have two classes: Cell class representing each matrix cell, and DeliveryArea representing the area the truck should navigate. See the skeleton below, just the class and the method signatures. We will complete the implementation in the next section.

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);
    }
}

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;
    }
}

Check out the full solution