Graphs: Dots and Lines

Everything is connected

A graph is a set of nodes (dots) joined by edges (lines). Trees are graphs, but graphs can have loops and no root. Real examples:

• Undirected: the edge works both ways (friendship).
• Directed: the edge has an arrow (a web link, a one-way street).
• Weighted: each edge has a number, like a distance (Module 16).

The adjacency list

The usual way to store a graph: for every node, a list of its neighbours. In Java, an ArrayList of ArrayLists:

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        int n = 5;                                       // people 1..5
        ArrayList<ArrayList<Integer>> friends = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) friends.add(new ArrayList<Integer>());   // index 0 unused

        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}};
        for (int[] e : edges) {
            friends.get(e[0]).add(e[1]);                 // undirected: add both ways
            friends.get(e[1]).add(e[0]);
        }
        for (int person = 1; person <= n; person++) {
            System.out.println(person + ": " + friends.get(person));
        }
    }
}

Output

1: [2, 3]
2: [1, 4]
3: [1, 4]
4: [2, 3, 5]
5: [4]

Memory is O(n + m) for n nodes and m edges, and listing a node's neighbours is as fast as it gets.

Tip: Another option is an adjacency matrix – a boolean[n][n] grid where g[u][v] says whether an edge exists. It answers “are u and v linked?” in O(1) but needs n² memory, so it's only good for small graphs.