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.

Watch this tutorial in Youtube

The assignment

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 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 problem is one of my favorite java assignments to practice. An excellent graph implementation example in Java of how using the correct data structure can turn a seemingly complex problem into something much more straightforward.

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]

How to Solve

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.

Plus, I will advise you to solve this problem following a test-driven approach, which means defining the function signature to do the calculation without writing the code. Then write some tests. And last, writing the code. Why writing tests? It will be much easier and quicker to check that things are working correctly.

Our 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.

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

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

See the completed solution in hellocodeclub.com

I hope you enjoyed the article and thanks for reading! Happy Coding!