Adjacency List Representation

Problem Statement

Write a Java program that implements an undirected graph using a jagged array as an adjacency list. The program should include methods to add edges between vertices and print the neighbors of each vertex. Test the implementation with a sample graph, including cases with varying numbers of vertices and edges, and ensure the graph correctly represents undirected connections (i.e., an edge from u to v implies an edge from v to u). You can visualize this as creating a map of friendships, where each person (vertex) has a list of friends (neighbors), and friendships are mutual.

Input:

• Number of vertices V (e.g., V = 4).
• Edges as pairs of vertices (e.g., (0, 1), (1, 2), (2, 3)). Output:
• For each vertex, print its neighbors as a list (e.g., for vertex 0: [1], for vertex 1: [0, 2], etc.). Constraints:
• 1 ≤ V ≤ 100 (number of vertices).
• Vertices are labeled from 0 to V-1.
• Edges are valid pairs of distinct vertices (u ≠ v).
• The graph is undirected and simple (no self-loops or multiple edges between the same vertices). Example:
• Input: V = 4, edges = [(0, 1), (1, 2), (2, 3), (0, 2)]
• Output:

  Vertex 0 neighbors: [1, 2]
  Vertex 1 neighbors: [0, 2]
  Vertex 2 neighbors: [1, 3, 0]
  Vertex 3 neighbors: [2]
  

• Explanation: The graph has 4 vertices. Vertex 0 is connected to 1 and 2, vertex 1 to 0 and 2, vertex 2 to 1, 3, and 0, and vertex 3 to 2.

Pseudocode

FUNCTION initializeGraph(V)
    CREATE jagged array adjList of size V
    FOR i from 0 to V - 1
        SET adjList[i] to empty array
    ENDFOR
    RETURN adjList
ENDFUNCTION

FUNCTION addEdge(adjList, u, v)
    IF adjList is null OR u < 0 OR u >= length of adjList OR v < 0 OR v >= length of adjList OR u equals v THEN
        RETURN
    ENDIF
    IF v not in adjList[u] THEN
        ADD v to adjList[u]
    ENDIF
    IF u not in adjList[v] THEN
        ADD u to adjList[v]
    ENDIF
ENDFUNCTION

FUNCTION printNeighbors(adjList)
    IF adjList is null OR adjList is empty THEN
        PRINT "Graph is empty"
        RETURN
    ENDIF
    FOR i from 0 to length of adjList - 1
        PRINT "Vertex i neighbors: " followed by adjList[i]
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET V to number of vertices
    CALL initializeGraph(V)
    SET edges to list of edge pairs
    FOR each (u, v) in edges
        CALL addEdge(adjList, u, v)
    ENDFOR
    CALL printNeighbors(adjList)
ENDFUNCTION

Algorithm Steps

1. Initialize Graph: a. Create a jagged array adjList of size V, where each element is an empty array (to store neighbors).
2. Add Edge: a. Validate inputs: check if adjList is null, or vertices u, v are out of bounds or equal (self-loop). b. Add v to adjList[u] if not already present (to avoid duplicates). c. Add u to adjList[v] if not already present (for undirected graph).
3. Print Neighbors: a. Check if adjList is null or empty. If so, print "Graph is empty". b. For each vertex i, print its index and the array of neighbors adjList[i].
4. In the main method, initialize a graph with a specified number of vertices, add edges from a sample edge list, and print the neighbors of each vertex.

Java Implementation

import java.util.ArrayList;

public class AdjacencyListRepresentation {
    // Initializes a graph with V vertices as a jagged array
    private ArrayList<Integer>[] adjList;

    // Constructor to initialize graph
    @SuppressWarnings("unchecked")
    public AdjacencyListRepresentation(int V) {
        adjList = (ArrayList<Integer>[]) new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adjList[i] = new ArrayList<>();
        }
    }

    // Adds an edge between vertices u and v
    public void addEdge(int u, int v) {
        // Validate inputs
        if (adjList == null || u < 0 || u >= adjList.length || v < 0 || v >= adjList.length || u == v) {
            return;
        }
        // Add v to u's list if not already present
        if (!adjList[u].contains(v)) {
            adjList[u].add(v);
        }
        // Add u to v's list if not already present (undirected)
        if (!adjList[v].contains(u)) {
            adjList[v].add(u);
        }
    }

    // Prints neighbors of each vertex
    public void printNeighbors() {
        if (adjList == null || adjList.length == 0) {
            System.out.println("Graph is empty");
            return;
        }
        for (int i = 0; i < adjList.length; i++) {
            System.out.print("Vertex " + i + " neighbors: [");
            for (int j = 0; j < adjList[i].size(); j++) {
                System.out.print(adjList[i].get(j));
                if (j < adjList[i].size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.println("]");
        }
    }

    // Main method to test the graph implementation
    public static void main(String[] args) {
        // Test case 1: Sample graph with 4 vertices
        System.out.println("Test case 1: Graph with 4 vertices");
        AdjacencyListRepresentation graph1 = new AdjacencyListRepresentation(4);
        int[][] edges1 = {{0, 1}, {1, 2}, {2, 3}, {0, 2}};
        for (int[] edge : edges1) {
            graph1.addEdge(edge[0], edge[1]);
        }
        graph1.printNeighbors();

        // Test case 2: Single vertex, no edges
        System.out.println("\nTest case 2: Single vertex");
        AdjacencyListRepresentation graph2 = new AdjacencyListRepresentation(1);
        graph2.printNeighbors();

        // Test case 3: Graph with 5 vertices, more edges
        System.out.println("\nTest case 3: Graph with 5 vertices");
        AdjacencyListRepresentation graph3 = new AdjacencyListRepresentation(5);
        int[][] edges3 = {{0, 1}, {0, 2}, {0, 3}, {1, 3}, {1, 4}, {2, 4}};
        for (int[] edge : edges3) {
            graph3.addEdge(edge[0], edge[1]);
        }
        graph3.printNeighbors();

        // Test case 4: Empty graph (0 vertices)
        System.out.println("\nTest case 4: Empty graph");
        AdjacencyListRepresentation graph4 = new AdjacencyListRepresentation(0);
        graph4.printNeighbors();
    }
}

Output

Running the main method produces:

Test case 1: Graph with 4 vertices
Vertex 0 neighbors: [1, 2]
Vertex 1 neighbors: [0, 2]
Vertex 2 neighbors: [1, 3, 0]
Vertex 3 neighbors: [2]

Test case 2: Single vertex
Vertex 0 neighbors: []

Test case 3: Graph with 5 vertices
Vertex 0 neighbors: [1, 2, 3]
Vertex 1 neighbors: [0, 3, 4]
Vertex 2 neighbors: [0, 4]
Vertex 3 neighbors: [0, 1]
Vertex 4 neighbors: [1, 2]

Test case 4: Empty graph
Graph is empty

Explanation:

• Test case 1: Graph with 4 vertices and edges (0,1), (1,2), (2,3), (0,2). Vertex 0 is connected to 1 and 2, etc.
• Test case 2: Single vertex with no edges, so its neighbor list is empty.
• Test case 3: Graph with 5 vertices and more edges, forming a connected structure.
• Test case 4: Empty graph (0 vertices) prints "Graph is empty".

How It Works

• Initialization: Creates a jagged array (ArrayList<Integer>[]) of size V, with each element as an empty ArrayList for neighbors.
• Add Edge: For edge (u, v), adds v to adjList[u] and u to adjList[v] if not already present, ensuring undirected edges without duplicates.
• Print Neighbors: Iterates through each vertex and prints its neighbor list.
• Example Trace (Test case 1):
  • Initialize: adjList = [[], [], [], []] for V = 4.
  • Add edge (0,1): adjList[0] = [1], adjList[1] = [0].
  • Add edge (1,2): adjList[1] = [0, 2], adjList[2] = [1].
  • Add edge (2,3): adjList[2] = [1, 3], adjList[3] = [2].
  • Add edge (0,2): adjList[0] = [1, 2], adjList[2] = [1, 3, 0].
  • Print: Vertex 0: [1, 2], Vertex 1: [0, 2], etc.
• Main Method: Tests with a 4-vertex graph, a single-vertex graph, a 5-vertex graph, and an empty graph.
• Adjacency List Property: Uses a jagged array for space efficiency, storing only actual neighbors.

Complexity Analysis Table

Note:

• V is the number of vertices, E is the number of edges.
• Initialize: O(V) to create V empty lists.
• Add Edge: O(1) average for ArrayList add and contains (amortized, assuming hash-based checks).
• Print Neighbors: O(V + E) to iterate through all vertices and their edges.
• Space: O(V + E) for the jagged array storing V lists and E edges (undirected edges stored twice).
• Worst case for dense graph: O(V^2) space if E ≈ V^2.

✅ Tip: Use ArrayList for dynamic neighbor lists to handle varying degrees. Test with sparse and dense graphs to verify correctness, including single-vertex and empty graphs.

⚠ Warning: Validate vertex indices to avoid ArrayIndexOutOfBoundsException. Ensure edges are not self-loops (u ≠ v) and check for duplicates to maintain a simple graph.