Step 2 of 6

33% Complete

Graph Representation

Learn different ways to represent graphs in code

Graph Representation Methods

Graphs can be represented in different ways, each with different trade-offs. The choice of representation affects the efficiency of operations and memory usage.

1. Adjacency List

Store a list of neighbors for each vertex. Most common representation for sparse graphs.

Adjacency List Implementation

public class AdjacencyListGraph {
    private List<Integer>[] adj;
    private int V;
    private int E;
    
    // Constructor
    public AdjacencyListGraph(int V) {
        this.V = V;
        this.E = 0;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    // Add edge (undirected)
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
        E++;
    }
    
    // Add edge (directed)
    public void addDirectedEdge(int u, int v) {
        adj[u].add(v);
        E++;
    }
    
    // Get neighbors of vertex
    public List<Integer> getNeighbors(int v) {
        return adj[v];
    }
    
    // Get all edges
    public List<String> getEdges() {
        List<String> edges = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            for (int neighbor : adj[i]) {
                edges.add(i + " - " + neighbor);
            }
        }
        return edges;
    }
    
    public static void main(String[] args) {
        AdjacencyListGraph g = new AdjacencyListGraph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        
        System.out.println("Neighbors of 0: " + g.getNeighbors(0));
        System.out.println("Neighbors of 2: " + g.getNeighbors(2));
    }
}

Advantages

Space efficient: O(V + E)
Fast to get neighbors: O(degree)
Good for sparse graphs
Natural for iterating edges

Disadvantages

Check edge existence: O(degree)
Potentially unbalanced lists

2. Adjacency Matrix

Store a 2D array where matrix[u][v] indicates if edge exists between u and v. Good for dense graphs with fast edge lookups.

Adjacency Matrix Implementation

public class AdjacencyMatrixGraph {
    private int[][] matrix;
    private int V;
    private int E;
    
    // Constructor
    public AdjacencyMatrixGraph(int V) {
        this.V = V;
        this.E = 0;
        matrix = new int[V][V];
        // Initialize with 0 (no edges)
    }
    
    // Add edge (undirected)
    public void addEdge(int u, int v) {
        if (matrix[u][v] == 0) {
            matrix[u][v] = 1;
            matrix[v][u] = 1;
            E++;
        }
    }
    
    // Add edge (directed)
    public void addDirectedEdge(int u, int v) {
        if (matrix[u][v] == 0) {
            matrix[u][v] = 1;
            E++;
        }
    }
    
    // Check if edge exists
    public boolean hasEdge(int u, int v) {
        return matrix[u][v] == 1;
    }
    
    // Get neighbors of vertex
    public List<Integer> getNeighbors(int v) {
        List<Integer> neighbors = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            if (matrix[v][i] == 1) {
                neighbors.add(i);
            }
        }
        return neighbors;
    }
    
    public static void main(String[] args) {
        AdjacencyMatrixGraph g = new AdjacencyMatrixGraph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        
        System.out.println("Edge 0-1 exists: " + g.hasEdge(0, 1));
        System.out.println("Edge 0-3 exists: " + g.hasEdge(0, 3));
        System.out.println("Neighbors of 0: " + g.getNeighbors(0));
    }
}

Advantages

Fast edge lookup: O(1)
Fast edge deletion: O(1)
Good for dense graphs
Simple to implement

Disadvantages

Space inefficient: O(V²)
Get neighbors: O(V) - must scan entire row
Wasteful for sparse graphs

3. Edge List

Store all edges as pairs of vertices. Simple but less efficient for most operations.

Edge List Implementation

public class EdgeListGraph {
    static class Edge {
        int u, v, weight;
        
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }
    
    private List<Edge> edges;
    private int V;
    
    // Constructor
    public EdgeListGraph(int V) {
        this.V = V;
        this.edges = new ArrayList<>();
    }
    
    // Add weighted edge
    public void addEdge(int u, int v, int weight) {
        edges.add(new Edge(u, v, weight));
    }
    
    // Get all edges
    public List<Edge> getEdges() {
        return edges;
    }
    
    // Get neighbors of vertex (O(E) - inefficient)
    public List<Integer> getNeighbors(int v) {
        List<Integer> neighbors = new ArrayList<>();
        for (Edge e : edges) {
            if (e.u == v) {
                neighbors.add(e.v);
            } else if (e.v == v) {
                neighbors.add(e.u);
            }
        }
        return neighbors;
    }
    
    public static void main(String[] args) {
        EdgeListGraph g = new EdgeListGraph(4);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 3, 4);
        
        System.out.println("All edges:");
        for (Edge e : g.getEdges()) {
            System.out.println(e.u + " - " + e.v + " (weight: " + e.weight + ")");
        }
    }
}

Advantages

Simple to understand
Good for algorithms that process all edges
Supports weighted edges naturally

Disadvantages

Get neighbors is O(E)
Check edge existence: O(E)
Inefficient for most operations

Weighted Graph Example

Weighted Adjacency List

public class WeightedGraph {
    static class Edge {
        int to, weight;
        
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    private List<Edge>[] adj;
    private int V;
    
    public WeightedGraph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    // Add weighted edge
    public void addEdge(int u, int v, int weight) {
        adj[u].add(new Edge(v, weight));
        adj[v].add(new Edge(u, weight));  // Undirected
    }
    
    // Get weighted neighbors
    public List<Edge> getNeighbors(int v) {
        return adj[v];
    }
    
    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph(4);
        g.addEdge(0, 1, 4);
        g.addEdge(0, 2, 2);
        g.addEdge(1, 2, 1);
        g.addEdge(1, 3, 5);
        g.addEdge(2, 3, 8);
        
        // Print weighted neighbors of vertex 0
        System.out.println("Neighbors of 0:");
        for (Edge e : g.getNeighbors(0)) {
            System.out.println("  to: " + e.to + ", weight: " + e.weight);
        }
    }
}

Comparison Table

Operation	Adjacency List	Adjacency Matrix	Edge List
Space	O(V+E)	O(V²)	O(E)
Add Edge	O(1)	O(1)	O(1)
Remove Edge	O(degree)	O(1)	O(E)
Check Edge	O(degree)	O(1)	O(E)
Get Neighbors	O(degree)	O(V)	O(E)
Best For	Sparse graphs	Dense graphs	Edge processing

When to Use Each Representation

Adjacency List

Most common choice for general-purpose graph algorithms like DFS, BFS, Dijkstra

Adjacency Matrix

Use when graph is dense or you need frequent edge lookups

Edge List

Use for algorithms that process all edges (Kruskal's, Bellman-Ford)

Key Takeaways

Adjacency list is most popular for sparse graphs (most real graphs)
Adjacency matrix better for dense graphs with frequent lookups
Each representation has different time/space trade-offs
Weighted graphs extend representations with weight information
Choose representation based on your specific use case
Most graph algorithms work with adjacency lists