Four types of Graph representations

In this post, we will go through four types of Graphs representations with code in Java and their applications.

Let’s go through four different types of graph representations with Java code examples and discuss their advantages for the operations of finding all edges, finding all adjacent nodes, and checking if an edge exists between two given nodes.

1. Edge List

An edge list is a simple way to represent a graph as a collection of all edges. Each edge is stored as a pair of vertices. This representation is compact but not the most efficient for querying adjacency or edge existence.

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

class Edge {
    int src;
    int dest;

    Edge(int src, int dest) {
        this.src = src;
        this.dest = dest;
    }

    @Override
    public String toString() {
        return "(" + src + " -> " + dest + ")";
    }
}

public class EdgeListGraph {
    List<Edge> edges;

    public EdgeListGraph() {
        this.edges = new ArrayList<>();
    }

    public void addEdge(int src, int dest) {
        edges.add(new Edge(src, dest));
    }

    public List<Edge> getEdges() {
        return edges;
    }
    
    public boolean hasEdge(int src, int dest) {
        for (Edge edge : edges) {
            if (edge.src == src && edge.dest == dest) {
                return true;
            }
        }
        return false;
    }
}

Space Complexity: O(E), where E is the number of edges. It is space-efficient for storing edges directly but does not store any adjacency information for nodes.

Time Complexity for common operations:

• Find all edges: O(1); simply return the list of edges.
• Find all adjacent nodes: O(E); requires scanning through all edges.
• Check if an edge exists: O(E); requires iterating through the list to find a match.
• Suitability: Best for applications where edge enumeration is needed, such as in algorithms that process all edges (e.g., Kruskal’s algorithm for MST). Not optimal for adjacency queries or checking edge existence frequently.

Pros:

• Simple and space-efficient for sparse graphs.
• Easy to implement and iterate over all edges.

Cons:

• Inefficient for adjacency and edge existence checks.
• Not suitable for dense graphs or where frequent adjacency queries are needed.

2. Adjacency List

An adjacency list represents the graph using an array or list of lists, where each vertex points to a list of its adjacent vertices. It is space-efficient for sparse graphs.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AdjacencyListGraph {
    Map<Integer, List<Integer>> adjList;

    public AdjacencyListGraph() {
        this.adjList = new HashMap<>();
    }

    public void addEdge(int src, int dest) {
        adjList.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);
    }

    public List<Integer> getAdjacentNodes(int node) {
        return adjList.getOrDefault(node, new ArrayList<>());
    }

    public boolean hasEdge(int src, int dest) {
        return adjList.containsKey(src) && adjList.get(src).contains(dest);
    }
}

Space Complexity: O(V+E), where V is the number of vertices. Efficient for sparse graphs as it only stores existing edges.

Time Complexity for Operations:

• Find all edges: O(V+E); iterate through all adjacency lists.
• Find all adjacent nodes: O(1) on average; direct access via the list.
• Check if an edge exists: O(degree of the node); scan through the list of adjacent nodes.
• Suitability: Ideal for most graph algorithms (e.g., BFS, DFS) and for graphs that are sparse. Works well when you need to iterate over neighbors of a node.

Pros:

• Space-efficient for sparse graphs.
• Direct and fast access to adjacent nodes.
• Easier to traverse for most graph algorithms.

Cons:

• Edge existence checks are slower compared to an adjacency matrix, especially if a node has a high degree.
• Not optimal for very dense graphs due to increased lookup time.

3. Adjacency Map

An adjacency map is similar to an adjacency list but uses a map of maps. This provides direct access to the edge.

import java.util.HashMap;
import java.util.Map;

public class AdjacencyMapGraph {
    Map<Integer, Map<Integer, Integer>> adjMap;

    public AdjacencyMapGraph() {
        this.adjMap = new HashMap<>();
    }

    public void addEdge(int src, int dest, int weight) {
        adjMap.computeIfAbsent(src, k -> new HashMap<>()).put(dest, weight);
    }

    public Map<Integer, Integer> getAdjacentNodes(int node) {
        return adjMap.getOrDefault(node, new HashMap<>());
    }

    public boolean hasEdge(int src, int dest) {
        return adjMap.containsKey(src) && adjMap.get(src).containsKey(dest);
    }
}

Space Complexity: O(V+E) in the average case, with some additional overhead for the map structure. This representation can be more memory-intensive than adjacency lists due to the underlying hash table.

Time Complexity for Operations:

• Find all edges: O(V+E); iterate through the map.
• Find all adjacent nodes: O(1); direct access via the map.
• Check if an edge exists: O(1) on average, assuming efficient hash function implementation.
• Suitability: Works well when you need fast lookups and potentially need to store additional information such as weights. Good for weighted graphs or when edge existence checks are common.

Pros:

• Fast lookup and edge existence checks.
• Supports weighted edges and additional metadata easily.
• More flexible and allows direct map operations for complex graph structures.

Cons:

• More space-intensive than an adjacency list due to the overhead of hash maps.
• Performance depends on the efficiency of the hash function (potential collisions).

4. Adjacency Matrix

An adjacency matrix uses a 2D array to represent the graph, where a cell at (i, j) indicates the presence of an edge from vertex i to vertex j. It uses O(V²) space and is most useful for dense graphs.

public class AdjacencyMatrixGraph {
    int[][] matrix;
    int size;

    public AdjacencyMatrixGraph(int size) {
        this.size = size;
        this.matrix = new int[size][size];
    }

    public void addEdge(int src, int dest) {
        matrix[src][dest] = 1; // 1 indicates an edge exists; modify for weighted graphs if needed.
    }

    public boolean hasEdge(int src, int dest) {
        return matrix[src][dest] != 0;
    }

    public void printAdjacentNodes(int node) {
        System.out.print("Adjacent nodes of " + node + ": ");
        for (int i = 0; i < size; i++) {
            if (matrix[node][i] != 0) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}

Space Complexity: O(V²), regardless of the number of edges. This is space-inefficient for sparse graphs, but it can be appropriate for dense graphs.

Time Complexity for Operations:

• Find all edges: O(V²); iterate through the entire matrix.
• Find all adjacent nodes: O(V); iterate over a row in the matrix.
• Check if an edge exists: O(1); direct access via matrix indexing.
• Suitability: Best suited for dense graphs where E is close to V², or when you need very fast edge existence checks.

Pros:

• Fastest edge existence check O(1)) of all representations.
• Simple to implement for small, dense graphs.
• Ideal for certain algorithms that require checking edge existence frequently.

Cons:

• High space complexity makes it impractical for sparse graphs.
• Iterating over neighbors or finding all edges requires O(V) or O(V²), which can be slow for large graphs.
• Does not inherently store edge weights unless modified (e.g., using non-zero values for weights).

Summary of Tradeoffs

Choosing the Right Representation:

• Use edge list for simple or edge-centric problems.
• Use adjacency list for traversal-heavy or sparse graph algorithms.
• Use adjacency map when fast lookups and flexibility (e.g., weighted graphs) are needed.
• Use adjacency matrix when edge existence checks need to be constant time and space isn’t a concern (dense graphs).

If you’re gearing up for coding interviews, Handbook for Coding Interviews book is the perfect prep guide. This book is packed with all the coding patterns and complete solutions to the most frequently asked coding interview questions.

If you found this post useful, please follow me on Medium. More to come.