Representing Graphs: Adjacency Matrix and List

1. What is a Graph?

At its core, a graph is a data structure used to model relationships. It consists of two main components:

• Vertices (or Nodes): The fundamental entities within the graph. Think of these as cities on a map, people in a social network, or devices in a computer network.
• Edges: The connections between pairs of vertices. These represent roads, friendships, or network cables.

Before we dive into representing them, it's crucial to understand a few key properties that define a graph's behavior. The happycoding.io article provides an excellent introduction to these concepts.

Understanding these distinctions is vital because your choice of representation will depend on them. For example, representing a directed, weighted graph is different from representing a simple, unweighted, undirected graph.

2. Representation 1: Adjacency Matrix

The first and most straightforward way to represent a graph is using an adjacency matrix. This is a 2D array, typically of size V x V (where V is the number of vertices).

The rules are simple:

• matrix[i][j] = 1 if there is an edge from vertex i to vertex j.
• matrix[i][j] = 0 if there is no edge.

For a weighted graph, instead of storing 1, you store the weight of the edge. A 0 or infinity can represent the absence of an edge.

For an undirected graph, the matrix will be symmetric across the main diagonal (since an edge from i to j implies an edge from j to i).

This video provides a great walkthrough of the concept and its implementation.

Pros and Cons of Adjacency Matrix

• Pros:
  • Fast Edge Lookup: Checking if an edge exists between two vertices i and j is an O(1) operation (just look up matrix[i][j]).
• Cons:
  • High Space Complexity: It requires O(V^2) space, regardless of the number of edges. This is very inefficient for sparse graphs (graphs with many vertices but few edges), which are common in practice.
  • Slow Neighbor Iteration: To find all neighbors of a vertex, you must iterate through its entire row, which takes O(V) time.

3. Representation 2: Adjacency List

The adjacency list is the most common way to represent graphs in competitive programming and technical interviews, primarily because it's more space-efficient for sparse graphs.

The concept is an array of lists. The list at index i stores all the vertices that are adjacent to vertex i.

In Java, this is typically implemented as:

• ArrayList<ArrayList<Integer>> adj;
• Or, more flexibly, Map<Integer, List<Integer>> adj;

Let's return to the video from 'take U forward' to see how this works.

For weighted graphs, you can't just store a list of integers. Instead, you'd store a list of objects or pairs, where each element contains the neighbor and the weight of the edge to it. A common Java implementation would be ArrayList<ArrayList<Pair<Integer, Integer>>>.

Pros and Cons of Adjacency List

• Pros:
  • Space Efficient: Requires O(V + E) space (where E is the number of edges). This is significantly better than O(V^2) for sparse graphs.
  • Fast Neighbor Iteration: Iterating through all neighbors of a vertex u is efficient, as you only traverse the list of its actual neighbors.
• Cons:
  • Slower Edge Lookup: To check if an edge exists between u and v, you have to search through u's adjacency list, which can take up to O(degree(u)) time in the worst case (where degree(u) is the number of neighbors).

4. Implementation in Java

In most programming challenges, you are given the graph as a list of edges. A common first step is to convert this input into a more usable format like an adjacency list.

A typical input format looks like this:

1. The first line contains two integers: N (number of vertices) and M (number of edges).
2. The next M lines each contain two integers, u and v, representing an edge between vertex u and vertex v.

The happycoding.io resource has an excellent section showing how to perform this conversion.

Here's a concise example of how to build an adjacency list for an undirected graph in Java, based on the pattern you just reviewed:

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

public class GraphRepresentation {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("Enter number of vertices (N) and edges (M):");
        int n = sc.nextInt(); // Number of vertices
        int m = sc.nextInt(); // Number of edges

        // Adjacency List: An ArrayList of ArrayLists.
        // We use n+1 size for 1-based indexing, which is common in problems.
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>(n + 1);

        // Initialize an empty list for each vertex.
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        System.out.println("Enter " + m + " edges (u v):");
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            // Since it's an undirected graph, add an edge from u to v
            adj.get(u).add(v);
            // AND an edge from v to u
            adj.get(v).add(u);
        }

        // Print the adjacency list to verify
        System.out.println("\nAdjacency List:");
        for (int i = 1; i <= n; i++) {
            System.out.print("Vertex " + i + ": ");
            for (Integer neighbor : adj.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
        sc.close();
    }
}

This code snippet is a template you can adapt for many graph problems. For a directed graph, you would simply omit the adj.get(v).add(u); line.

Conclusion

You've now taken your first and most crucial step into the world of graphs. Understanding how to represent them is the foundation upon which all other graph algorithms are built.

Key Takeaways:

• A graph is defined by its vertices and edges, and can be directed/undirected and weighted/unweighted.
• An Adjacency Matrix uses O(V^2) space and offers O(1) edge lookups. It is best for dense graphs where E is close to V^2.
• An Adjacency List uses O(V + E) space and is efficient for iterating over neighbors. It is the preferred choice for sparse graphs and most competitive programming problems.
• You should be comfortable converting a standard edge-list input into an adjacency list representation in Java.

Preview of the Next Lesson:
Now that we know how to store a graph, how do we explore it? In the next lesson, we will learn our first formal graph traversal algorithm: Breadth-First Search (BFS). We'll use the adjacency list you learned to build today to implement BFS, which explores the graph level by level and is the key to finding the shortest path in unweighted graphs.