Java Coding Test Course, Representation of Graphs

Hello! Today we will take a closer look at graph representation which is frequently asked in coding tests using Java, and solve related algorithm problems. Graphs are a crucial data structure for solving given problems, consisting of vertices and edges. There are various ways to represent graphs, and in this article, we will explain the Adjacency List and Adjacency Matrix methods.

Graph Representation Methods

1. Adjacency List

An adjacency list is a way of storing a list of adjacent vertices for each vertex. It is usually implemented using arrays or lists. This method is very memory efficient and is useful in operations that proceed relatively slowly.

class Graph {
    private int vertices; // number of vertices
    private LinkedList[] adjList; // adjacency list
    
    // graph constructor
    public Graph(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // method to add an edge
    public void addEdge(int source, int destination) {
        adjList[source].add(destination);
        // If it's an undirected graph, you should also add the next line
        // adjList[destination].add(source);
    }
}

2. Adjacency Matrix

An adjacency matrix is a way of representing a graph using a 2D array. This method allows you to check the existence of an edge in O(1) time complexity, but it has high space complexity and can be inefficient for graphs of variable sizes.

class Graph {
    private int vertices;
    private int[][] adjMatrix;

    // graph constructor
    public Graph(int v) {
        vertices = v;
        adjMatrix = new int[v][v];
    }

    // method to add an edge
    public void addEdge(int source, int destination) {
        adjMatrix[source][destination] = 1;
        // For undirected graphs
        // adjMatrix[destination][source] = 1;
    }
}

Problem: Building Bridges

Now let’s solve an actual problem. The given problem is Building Bridges.

Problem Description

Given N points on a 2D plane, we want to construct bridges so that every point can be connected to each other.
The length of the bridge is the Euclidean distance between two points.
Find the length of the shortest path. Note that two points cannot be connected again during the bridge construction process.

Input

• The first line contains the number of points N (1 ≤ N ≤ 100).
• The second line contains the coordinates of each point. (x1, y1), (x2, y2), …, (xN, yN)

Output

Print the length of the shortest path. (Up to 2 decimal places)

Problem Solving Approach

To solve the problem, I will approach it in the following order:

1. Receive coordinates and store the points.
2. Calculate the distances between the coordinates to find the bridge lengths.
3. Use Dijkstra’s algorithm to find the shortest path.
4. Print the result up to the second decimal place.

Java Code Implementation

import java.util.*;

class Point {
    int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    double distance(Point p) {
        return Math.sqrt(Math.pow(this.x - p.x, 2) + Math.pow(this.y - p.y, 2));
    }
}

class Graph {
    private int vertices;
    private List points;
    private double[][] adjMatrix;

    public Graph(int v) {
        vertices = v;
        points = new ArrayList<>();
        adjMatrix = new double[v][v];
    }

    public void addPoint(Point p) {
        points.add(p);
        int idx = points.size() - 1;
        for (int i = 0; i < idx; i++) {
            double dist = points.get(i).distance(p);
            adjMatrix[i][idx] = dist;
            adjMatrix[idx][i] = dist; // undirected edge
        }
    }

    public double dijkstra() {
        double[] dist = new double[vertices];
        boolean[] visited = new boolean[vertices];

        Arrays.fill(dist, Double.MAX_VALUE);
        dist[0] = 0; // starting point

        for (int i = 0; i < vertices - 1; i++) {
            int minIndex = findMinIndex(dist, visited);
            visited[minIndex] = true;

            for (int j = 0; j < vertices; j++) {
                if (!visited[j] && adjMatrix[minIndex][j] != 0 &&
                    dist[minIndex] + adjMatrix[minIndex][j] < dist[j]) {
                    dist[j] = dist[minIndex] + adjMatrix[minIndex][j];
                }
            }
        }

        return dist[vertices - 1]; // distance to the endpoint
    }

    private int findMinIndex(double[] dist, boolean[] visited) {
        double min = Double.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < vertices; i++) {
            if (!visited[i] && dist[i] < min) {
                min = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Graph graph = new Graph(n);

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph.addPoint(new Point(x, y));
        }

        double result = graph.dijkstra();
        System.out.printf("%.2f\n", result);
    }
}

Conclusion

Today, we explored graph representation methods and solved an algorithm problem.
Through this problem, we learned how to handle graphs and how to compute distances between points, as well as implement the shortest path algorithm using adjacency lists and adjacency matrices.
Graphs are a common concept in real life and are very useful in solving complex problems.

Next time, we will look into topics related to search algorithms. Thank you!