Create a Graph, print it

Problem Statement

Given a number of vertices V and a list of edges, create a graph and print its adjacency representation. The graph is undirected.

Example:

• Input: V = 5, Edges = [[0,1], [0,4], [1,2], [1,3], [1,4], [2,3], [3,4]]
• Output: 0 -> 1 4 1 -> 0 2 3 4 2 -> 1 3 3 -> 1 2 4 4 -> 0 1 3

Noob-Friendly Explanation

Think of a graph like a map of cities connected by roads. Each city is a vertex (or node) and each road is an edge. When we "create a graph," we're basically writing down which cities are connected to which. When we "print" it, we go through every city and list all the cities you can drive to directly from there.

There are two popular ways to store this information:

1. Adjacency Matrix — A big table where rows and columns are cities, and we mark "1" if there's a road.
2. Adjacency List — For each city, we just keep a list of neighbors.

Approach 1: Brute Force (Adjacency Matrix)

Intuition

Use a 2D array (like a table) of size V×V. If there's an edge between vertex i and vertex j, set matrix[i][j] = 1 and matrix[j][i] = 1.

Algorithm

1. Create a 2D array of size V×V, initialized to 0.
2. For each edge (u, v), set matrix[u][v] = 1 and matrix[v][u] = 1.
3. To print, iterate through each row and print the indices where the value is 1.

public class GraphMatrix {
    public static void createAndPrint(int V, int[][] edges) {
        int[][] matrix = new int[V][V];

        // Fill the adjacency matrix
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            matrix[u][v] = 1;
            matrix[v][u] = 1; // undirected graph
        }

        // Print the graph
        for (int i = 0; i < V; i++) {
            System.out.print(i + " -> ");
            for (int j = 0; j < V; j++) {
                if (matrix[i][j] == 1) {
                    System.out.print(j + " ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int V = 5;
        int[][] edges = {{0,1},{0,4},{1,2},{1,3},{1,4},{2,3},{3,4}};
        createAndPrint(V, edges);
    }
}

Complexity Analysis

• Time Complexity: O(V + E) for building, O(V^2) for printing — we must scan every cell in the matrix to print.
• Space Complexity: O(V^2) — the matrix always takes V×V space regardless of how many edges there are.

Approach 2: Optimal (Adjacency List)

Intuition

Instead of a big table, store only the actual neighbors for each vertex in a list. This saves space when the graph doesn't have too many edges (sparse graph).

Algorithm

1. Create an array of lists, one list per vertex.
2. For each edge (u, v), add v to the list of u and u to the list of v.
3. To print, iterate through each vertex's list.

import java.util.ArrayList;
import java.util.List;

public class GraphList {
    public static void createAndPrint(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Fill the adjacency list
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u); // undirected graph
        }

        // Print the graph
        for (int i = 0; i < V; i++) {
            System.out.print(i + " -> ");
            for (int neighbor : adj.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int V = 5;
        int[][] edges = {{0,1},{0,4},{1,2},{1,3},{1,4},{2,3},{3,4}};
        createAndPrint(V, edges);
    }
}

Complexity Analysis

• Time Complexity: O(V + E) — we visit each vertex and each edge once while printing.
• Space Complexity: O(V + E) — we only store the edges that actually exist.