Graph Representation

A Graph is a non-linear data structure consisting of Nodes (vertices) and Edges. Edges are lines or arcs that connect any two nodes in the graph. Graphs can be directed or undirected.

Visual Representation

There are two primary ways to represent a graph programmatically.

1. Adjacency Matrix

An adjacency matrix is a 2D array of size V x V where V is the number of vertices in a graph.

• matrix[i][j] = 1 indicates there is an edge between vertex i and j.
• Time Complexity: O(1) to query edge, Space: O(V^2). Use for dense graphs.

public class GraphMatrix {
    private int adjMatrix[][];
    private int numVertices;

    public GraphMatrix(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new int[numVertices][numVertices];
    }

    public void addEdge(int i, int j) {
        adjMatrix[i][j] = 1;
        adjMatrix[j][i] = 1; // Undirected
    }
}

2. Adjacency List

An adjacency list is an array of Linked Lists. The size of the array is equal to the number of vertices. An array element i points to a linked list containing all vertices adjacent to i.

• Space: O(V + E). Much better for sparse graphs.

import java.util.LinkedList;

public class GraphList {
    private int vertices;
    private LinkedList<Integer> adjListArray[];

    // Constructor
    public GraphList(int V) {
        vertices = V;
        adjListArray = new LinkedList[V];

        // Create a new list for each vertex
        for (int i = 0; i < V; i++) {
            adjListArray[i] = new LinkedList<>();
        }
    }

    // Adds an edge to an undirected graph
    public void addEdge(int src, int dest) {
        adjListArray[src].add(dest);
        adjListArray[dest].add(src); // Since it's undirected
    }
}