This Java program demonstrates the implementation of a graph using both an adjacency list and an adjacency matrix. This allows for a comparison of two primary methods of graph representation in terms of space and time efficiency.

Java Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

class Graph {
    private int V;   // Number of vertices
    private LinkedList<Integer> adjList[]; // Adjacency List
    private int adjMatrix[][]; // Adjacency Matrix

    public Graph(int V) {
        this.V = V;
        adjList = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            adjList[i] = new LinkedList<>();
        }
        
        adjMatrix = new int[V][V];
    }

    public void addEdgeList(int v, int w) {
        adjList[v].add(w);
        adjList[w].add(v); // Add w to v's list and vice versa for undirected graph
    }

    public void addEdgeMatrix(int v, int w) {
        adjMatrix[v][w] = 1;
        adjMatrix[w][v] = 1; // Mark the edges from v to w and w to v as true
    }

    public void printAdjList() {
        System.out.println("Adjacency List:");
        for (int i = 0; i < V; i++) {
            System.out.print(i + ": ");
            for (int node : adjList[i]) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }

    public void printAdjMatrix() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

public class GraphDemo {
    public static void main(String[] args) {
        Graph g = new Graph(4); // Create a graph with 4 vertices

        g.addEdgeList(0, 1);
        g.addEdgeList(0, 2);
        g.addEdgeList(1, 2);
        g.addEdgeList(2, 3);

        g.addEdgeMatrix(0, 1);
        g.addEdgeMatrix(0, 2);
        g.addEdgeMatrix(1, 2);
        g.addEdgeMatrix(2, 3);

        g.printAdjList();
        g.printAdjMatrix();
    }
}

Explanation of the Code

The program defines a Graph class to represent the graph using both an adjacency list and an adjacency matrix:

• Graph Constructor: Initializes the adjacency list and matrix for the number of vertices provided.
• addEdgeList and addEdgeMatrix Methods: These methods are used to add edges between vertices in the adjacency list and matrix, respectively.
• printAdjList and printAdjMatrix Methods: These methods display the graph as represented by the adjacency list and matrix, showcasing the graph’s structure visually in the console.

This dual representation in a single program provides insight into the trade-offs between the two methods, including the ease of edge insertion and space complexity.