Graph Connectivity

Problem Statement

Write a Java program that implements a graph using an adjacency list and checks if the graph is connected, meaning all vertices are reachable from a starting vertex, using Depth-First Search (DFS). The graph is undirected, and connectivity is determined by checking if a DFS from any vertex visits all vertices. The program should test the connectivity check with various graphs, including connected, disconnected, empty, and single-vertex graphs. You can visualize this as exploring a network of cities connected by roads, ensuring you can travel from one city to all others.

Input:

• An undirected graph represented by an adjacency list, with vertices as integers (0 to n-1).
• The number of vertices n and a list of edges (pairs of vertices). Output: A boolean indicating whether the graph is connected, and a string representation of the graph’s adjacency list for clarity. Constraints:
• The number of vertices n is between 0 and 10^5.
• Edges are pairs of integers [u, v] where 0 ≤ u, v < n.
• The graph is undirected (edge [u, v] implies [v, u]). Example:
• Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
• Output: Connected = true, "Adjacency List: {0=[1], 1=[0, 2], 2=[1, 3], 3=[2, 4], 4=[3]}"
• Explanation: All vertices are reachable from vertex 0.
• Input: n = 5, edges = [[0, 1], [2, 3]]
• Output: Connected = false, "Adjacency List: {0=[1], 1=[0], 2=[3], 3=[2], 4=[]}"
• Explanation: Vertex 4 is unreachable, so the graph is disconnected.
• Input: n = 0, edges = []
• Output: Connected = true, "Adjacency List: {}"
• Explanation: An empty graph is considered connected.

Pseudocode

FUNCTION createGraph(n, edges)
    CREATE adjList as new HashMap
    FOR i from 0 to n-1
        SET adjList[i] to empty list
    ENDFOR
    FOR each edge [u, v] in edges
        ADD v to adjList[u]
        ADD u to adjList[v]
    ENDFOR
    RETURN adjList
ENDFUNCTION

FUNCTION isConnected(adjList, n)
    IF n is 0 THEN
        RETURN true
    ENDIF
    CREATE visited as boolean array of size n, initialized to false
    FUNCTION dfs(vertex)
        SET visited[vertex] to true
        FOR each neighbor in adjList[vertex]
            IF NOT visited[neighbor] THEN
                CALL dfs(neighbor)
            ENDIF
        ENDFOR
    ENDFUNCTION
    CALL dfs(0)
    FOR i from 0 to n-1
        IF NOT visited[i] THEN
            RETURN false
        ENDIF
    ENDFOR
    RETURN true
ENDFUNCTION

FUNCTION toString(adjList)
    CREATE result as new StringBuilder
    APPEND "Adjacency List: {" to result
    FOR each vertex in adjList
        APPEND vertex and "=" and adjList[vertex] to result
        IF vertex is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "}" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (n, edges) pairs
    FOR each testCase in testCases
        PRINT test case details
        SET adjList to createGraph(testCase.n, testCase.edges)
        CALL isConnected(adjList, testCase.n)
        PRINT connected result and graph using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define createGraph: a. Create a HashMap adjList mapping vertices to lists of neighbors. b. Initialize empty lists for vertices 0 to n-1. c. Add edges bidirectionally (u→v, v→u).
2. Define isConnected: a. If n = 0, return true (empty graph is connected). b. Use DFS starting from vertex 0:
   • Mark vertex as visited.
   • Recursively visit unvisited neighbors. c. Check if all vertices are visited; return false if any are not.
3. Define toString: a. Convert adjacency list to a string, e.g., "{0=[1], 1=[0, 2], ...}".
4. In main, test with: a. A connected graph. b. A disconnected graph. c. An empty graph (n = 0). d. A single-vertex graph.

Java Implementation

import java.util.*;

public class GraphConnectivity {
    // Creates adjacency list representation of the graph
    private Map<Integer, List<Integer>> createGraph(int n, int[][] edges) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            adjList.get(u).add(v);
            adjList.get(v).add(u); // Undirected graph
        }
        return adjList;
    }

    // Checks if the graph is connected using DFS
    public boolean isConnected(Map<Integer, List<Integer>> adjList, int n) {
        if (n == 0) {
            return true;
        }
        boolean[] visited = new boolean[n];
        dfs(0, adjList, visited);
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    private void dfs(int vertex, Map<Integer, List<Integer>> adjList, boolean[] visited) {
        visited[vertex] = true;
        for (int neighbor : adjList.get(vertex)) {
            if (!visited[neighbor]) {
                dfs(neighbor, adjList, visited);
            }
        }
    }

    // Converts graph to string (adjacency list)
    public String toString(Map<Integer, List<Integer>> adjList) {
        StringBuilder result = new StringBuilder("Adjacency List: {");
        List<Integer> vertices = new ArrayList<>(adjList.keySet());
        Collections.sort(vertices); // For consistent output
        for (int i = 0; i < vertices.size(); i++) {
            int vertex = vertices.get(i);
            result.append(vertex).append("=").append(adjList.get(vertex));
            if (i < vertices.size() - 1) {
                result.append(", ");
            }
        }
        result.append("}");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int n;
        int[][] edges;

        TestCase(int n, int[][] edges) {
            this.n = n;
            this.edges = edges;
        }
    }

    // Main method to test graph connectivity
    public static void main(String[] args) {
        GraphConnectivity connectivityChecker = new GraphConnectivity();

        // Test cases
        TestCase[] testCases = {
            // Connected graph: 0-1-2-3-4
            new TestCase(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 4}}),
            // Disconnected graph: 0-1, 2-3, 4 isolated
            new TestCase(5, new int[][]{{0, 1}, {2, 3}}),
            // Empty graph
            new TestCase(0, new int[][]{}),
            // Single vertex
            new TestCase(1, new int[][]{})
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Vertices: " + testCases[i].n);
            System.out.println("Edges: " + Arrays.deepToString(testCases[i].edges));
            Map<Integer, List<Integer>> adjList = connectivityChecker.createGraph(testCases[i].n, testCases[i].edges);
            boolean isConnected = connectivityChecker.isConnected(adjList, testCases[i].n);
            System.out.println("Connected: " + isConnected);
            System.out.println(connectivityChecker.toString(adjList) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Vertices: 5
Edges: [[0, 1], [1, 2], [2, 3], [3, 4]]
Connected: true
Adjacency List: {0=[1], 1=[0, 2], 2=[1, 3], 3=[2, 4], 4=[3]}

Test case 2:
Vertices: 5
Edges: [[0, 1], [2, 3]]
Connected: false
Adjacency List: {0=[1], 1=[0], 2=[3], 3=[2], 4=[]}

Test case 3:
Vertices: 0
Edges: []
Connected: true
Adjacency List: {}

Test case 4:
Vertices: 1
Edges: []
Connected: true
Adjacency List: {0=[]}

Explanation:

• Test case 1: All vertices are reachable from 0 (0→1→2→3→4), so connected.
• Test case 2: Vertex 4 is isolated, so disconnected.
• Test case 3: Empty graph is connected by definition.
• Test case 4: Single vertex is connected (no edges needed).

How It Works

• createGraph: Builds an adjacency list using a HashMap, adding undirected edges (u→v, v→u).
• isConnected:
  • Returns true for n = 0 (empty graph).
  • Runs DFS from vertex 0, marking visited vertices.
  • Checks if all vertices are visited; returns false if any are not.
• dfs: Marks current vertex, recursively visits unvisited neighbors.
• toString: Formats adjacency list as a string, sorting vertices for consistency.
• Example Trace (Test case 1):
  • DFS from 0: Visit 0, 1, 2, 3, 4 (via 0→1→2→3→4).
  • All vertices visited, return true.
• Main Method: Tests connected graph, disconnected graph, empty graph, and single vertex.

Complexity Analysis Table

Note:

• n is the number of vertices, e is the number of edges.
• Time complexity: O(n + e) for createGraph (initialize lists and add edges); O(n + e) for isConnected (DFS visits each vertex and edge once); O(n log n + e) for toString (sorting vertices).
• Space complexity: O(n + e) for createGraph and toString (adjacency list); O(n) for isConnected (visited array and recursion stack).
• Worst case: O(n + e) time and space for dense graphs.

✅ Tip: Use DFS to efficiently explore all reachable vertices from a starting point. For undirected graphs, a single DFS from any vertex is sufficient to check connectivity.

⚠ Warning: Ensure the graph is undirected by adding edges both ways. Handle edge cases like empty graphs or isolated vertices to avoid incorrect connectivity results.