Are These Two Friends? Adjacency Lists and Grids

Answer "are these two already friends?" in one step without running out of memory, before every Add friend button: why reading a friend list and a box for every pair both fall short at a million people, and how to choose between an adjacency list, a set per person and an adjacency matrix.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Store a graph as an adjacency list or an adjacency matrix
  • Choose between an adjacency list and an adjacency matrix from their costs

Key takeaways

  • Checking a friend list reads up to the whole list, O(k), and a grid with a box for every pair needs V² boxes, about a million million for a million people.
  • An adjacency list keeps, for each vertex, the list of its neighbors, like a page per person in an address book.
  • An adjacency matrix is a grid with a row and a column for every vertex, and a mark where two vertices are joined; it answers "are these two joined?" in one look, O(1).
  • Most real graphs connect each vertex to only a few others, so the adjacency list is the usual choice, and keeping each person's neighbors in a set makes the pair check O(1) on average too.
  • A grid earns its space when the graph is small or dense, or when checking pairs is almost the only job.

Before this: Who Knows Whom? When Anything Can Connect: Graphs kept a page of friends per person. Listing a person's friends is quick, but checking for one name means reading down the page.

The social app has a new rule. Before it shows an Add friend button on someone's profile, it checks: are these two already friends? Every profile anyone opens asks that question once, and the app's busiest hour opens about 2 million profiles. The app has 1,000,000 people. Most have about 200 friends; a few, like a singer who joined to talk to fans, have 5 million followers.

What would you try?

Read one person's page. Turn to Dev's page and look for Fay. For an ordinary person that's up to 200 names, O(k). But open the singer's profile and her page has 5 million names: answering "are you already a fan?" reads up to 5 million, and the busiest hour does it again for every fan who looks.

Keep a box for every pair. Picture the mileage chart in a printed road atlas: every town down the side, every town across the top, and the miles in the box where a row meets a column. Do that for people: a 1 in the box where Dev's row meets Fay's column if they're friends, a 0 if not. Now every check is one look, O(1), however famous anyone is. But a million people means 1,000,000 × 1,000,000 boxes: a million million, about a terabyte even at one byte a box. Each person has about 200 friends, so about 999,800 of the million boxes in their row hold a 0.

Keep each person's friends in a set. The page per person stays, but each page is a set (Have I Seen This Before? Sets) instead of a list. "Is Fay on Dev's page?" is one hash lookup, O(1) on average, even on the singer's page, and the memory is still only the friendships that exist.

What we tried Are these two friends? Memory for a million people Where it breaks
A list of friends per person O(k): up to 5 million reads about 200 million names famous people
A box for every pair O(1): one box a million million boxes memory
A set of friends per person O(1) on average about 200 million names nowhere so far

The questions that lead to it

Which question does the app ask most? "Are these two friends?" before every button, and "who are this person's friends?" for every "people you may know" box. Both have to be fast.

How many boxes would the grid need, and how many would hold a 1? A million million boxes, and only about 200 million 1s: one box in 5,000. The grid spends almost all its memory saying "no".

So what should the storage hold? Only the friendships that exist, in a form that answers "is this one there?" without reading. That's the page per person, with each page as a set.

How they got their names

Both ways of storing a graph are old enough to have textbook names, and you'll hear them from teammates and interviewers.

  • The page per person is an adjacency list: for each vertex, the vertices next to it ("adjacent" means "next to"). Its pages can be lists or sets; the name stays the same.
  • The grid is an adjacency matrix ("matrix" is the math word for a grid of numbers). For a two-way graph it's a mirror image: Dev's row, Fay's column and Fay's row, Dev's column hold the same mark. For a one-way graph, only the box in the follower's row is marked. For a weighted graph, the box holds the weight instead of a 1.

The chapter's eight-person network stored two ways, side by side: on the left, an adjacency list with a row per person and their friends' names after it, such as Dev followed by Ben, Cara and Eli; on the right, an 8 by 8 grid with the people's first letters A to H along the top and down the side, a 1 in each box where two people are friends and a 0 everywhere else, with the 1s mirrored across the diagonal

Both, in code

This program stores the chapter's eight people both ways, prints the grid, then asks both the same question: are Dev and Fay friends?

string[] people = { "Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana" };
(string, string)[] friendships = { ("Ava", "Ben"), ("Ava", "Cara"), ("Ben", "Dev"), ("Cara", "Dev"), ("Dev", "Eli"), ("Eli", "Fay"), ("Gus", "Hana") };

Dictionary<string, List<string>> friendsOf = new Dictionary<string, List<string>>();
Dictionary<string, int> position = new Dictionary<string, int>();
for (int i = 0; i < people.Length; i++)
{
    friendsOf[people[i]] = new List<string>();
    position[people[i]] = i;
}
int[,] grid = new int[people.Length, people.Length];

foreach ((string first, string second) in friendships)
{
    friendsOf[first].Add(second);
    friendsOf[second].Add(first);
    grid[position[first], position[second]] = 1;
    grid[position[second], position[first]] = 1;
}

string header = "    ";
foreach (string person in people)
{
    header += " " + person[0];
}
Console.WriteLine(header);
for (int row = 0; row < people.Length; row++)
{
    string line = people[row].PadRight(4);
    for (int column = 0; column < people.Length; column++)
    {
        line += " " + grid[row, column];
    }
    Console.WriteLine(line);
}

bool byList = friendsOf["Dev"].Contains("Fay");
bool byGrid = grid[position["Dev"], position["Fay"]] == 1;
Console.WriteLine("Dev and Fay, by list: " + (byList ? "yes" : "no") + ", after reading " + friendsOf["Dev"].Count + " names");
Console.WriteLine("Dev and Fay, by grid: " + (byGrid ? "yes" : "no") + ", after reading 1 box");
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
String[] people = {"Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"};
String[][] friendships = {{"Ava", "Ben"}, {"Ava", "Cara"}, {"Ben", "Dev"}, {"Cara", "Dev"}, {"Dev", "Eli"}, {"Eli", "Fay"}, {"Gus", "Hana"}};

void main() {
    Map<String, List<String>> friendsOf = new LinkedHashMap<>();
    Map<String, Integer> position = new HashMap<>();
    for (int i = 0; i < people.length; i++) {
        friendsOf.put(people[i], new ArrayList<>());
        position.put(people[i], i);
    }
    int[][] grid = new int[people.length][people.length];

    for (String[] pair : friendships) {
        friendsOf.get(pair[0]).add(pair[1]);
        friendsOf.get(pair[1]).add(pair[0]);
        grid[position.get(pair[0])][position.get(pair[1])] = 1;
        grid[position.get(pair[1])][position.get(pair[0])] = 1;
    }

    String header = "    ";
    for (String person : people) {
        header += " " + person.charAt(0);
    }
    IO.println(header);
    for (int row = 0; row < people.length; row++) {
        String line = String.format("%-4s", people[row]);
        for (int column = 0; column < people.length; column++) {
            line += " " + grid[row][column];
        }
        IO.println(line);
    }

    boolean byList = friendsOf.get("Dev").contains("Fay");
    boolean byGrid = grid[position.get("Dev")][position.get("Fay")] == 1;
    IO.println("Dev and Fay, by list: " + (byList ? "yes" : "no") + ", after reading " + friendsOf.get("Dev").size() + " names");
    IO.println("Dev and Fay, by grid: " + (byGrid ? "yes" : "no") + ", after reading 1 box");
}
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
people = ["Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"]
friendships = [("Ava", "Ben"), ("Ava", "Cara"), ("Ben", "Dev"), ("Cara", "Dev"), ("Dev", "Eli"), ("Eli", "Fay"), ("Gus", "Hana")]

friends_of = {}
position = {}
for i, person in enumerate(people):
    friends_of[person] = []
    position[person] = i
grid = [[0] * len(people) for _ in people]

for first, second in friendships:
    friends_of[first].append(second)
    friends_of[second].append(first)
    grid[position[first]][position[second]] = 1
    grid[position[second]][position[first]] = 1

header = "    "
for person in people:
    header += " " + person[0]
print(header)
for row, person in enumerate(people):
    line = f"{person:<4}"
    for cell in grid[row]:
        line += f" {cell}"
    print(line)

by_list = "Fay" in friends_of["Dev"]
by_grid = grid[position["Dev"]][position["Fay"]] == 1
print(f"Dev and Fay, by list: {'yes' if by_list else 'no'}, after reading {len(friends_of['Dev'])} names")
print(f"Dev and Fay, by grid: {'yes' if by_grid else 'no'}, after reading 1 box")
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
const people = ["Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"];
const friendships = [["Ava", "Ben"], ["Ava", "Cara"], ["Ben", "Dev"], ["Cara", "Dev"], ["Dev", "Eli"], ["Eli", "Fay"], ["Gus", "Hana"]];

const friendsOf = new Map();
const position = new Map();
people.forEach((person, i) => {
  friendsOf.set(person, []);
  position.set(person, i);
});
const grid = people.map(() => new Array(people.length).fill(0));

for (const [first, second] of friendships) {
  friendsOf.get(first).push(second);
  friendsOf.get(second).push(first);
  grid[position.get(first)][position.get(second)] = 1;
  grid[position.get(second)][position.get(first)] = 1;
}

let header = "    ";
for (const person of people) {
  header += ` ${person[0]}`;
}
console.log(header);
people.forEach((person, row) => {
  let line = person.padEnd(4);
  for (const cell of grid[row]) {
    line += ` ${cell}`;
  }
  console.log(line);
});

const byList = friendsOf.get("Dev").includes("Fay");
const byGrid = grid[position.get("Dev")][position.get("Fay")] === 1;
console.log(`Dev and Fay, by list: ${byList ? "yes" : "no"}, after reading ${friendsOf.get("Dev").length} names`);
console.log(`Dev and Fay, by grid: ${byGrid ? "yes" : "no"}, after reading 1 box`);
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box
const people: string[] = ["Ava", "Ben", "Cara", "Dev", "Eli", "Fay", "Gus", "Hana"];
const friendships: [string, string][] = [["Ava", "Ben"], ["Ava", "Cara"], ["Ben", "Dev"], ["Cara", "Dev"], ["Dev", "Eli"], ["Eli", "Fay"], ["Gus", "Hana"]];

const friendsOf = new Map<string, string[]>();
const position = new Map<string, number>();
people.forEach((person, i) => {
  friendsOf.set(person, []);
  position.set(person, i);
});
const grid: number[][] = people.map(() => new Array<number>(people.length).fill(0));

for (const [first, second] of friendships) {
  friendsOf.get(first)!.push(second);
  friendsOf.get(second)!.push(first);
  grid[position.get(first)!][position.get(second)!] = 1;
  grid[position.get(second)!][position.get(first)!] = 1;
}

let header = "    ";
for (const person of people) {
  header += ` ${person[0]}`;
}
console.log(header);
people.forEach((person, row) => {
  let line = person.padEnd(4);
  for (const cell of grid[row]) {
    line += ` ${cell}`;
  }
  console.log(line);
});

const byList = friendsOf.get("Dev")!.includes("Fay");
const byGrid = grid[position.get("Dev")!][position.get("Fay")!] === 1;
console.log(`Dev and Fay, by list: ${byList ? "yes" : "no"}, after reading ${friendsOf.get("Dev")!.length} names`);
console.log(`Dev and Fay, by grid: ${byGrid ? "yes" : "no"}, after reading 1 box`);
     A B C D E F G H
Ava  0 1 1 0 0 0 0 0
Ben  1 0 0 1 0 0 0 0
Cara 1 0 0 1 0 0 0 0
Dev  0 1 1 0 1 0 0 0
Eli  0 0 0 1 0 1 0 0
Fay  0 0 0 0 1 0 0 0
Gus  0 0 0 0 0 0 0 1
Hana 0 0 0 0 0 0 1 0
Dev and Fay, by list: no, after reading 3 names
Dev and Fay, by grid: no, after reading 1 box

The ! after get(...) in the TypeScript tab tells the checker "this key is there": a Map's get could return undefined, and here every person was added first.

Count the zeros: 64 boxes for 7 friendships. The list read Dev's 3 friends to say "no"; the grid read one box. That's the whole trade, and at a million people it decides everything.

Your language's set per person

To make the list's check one step, change each page from a list to a set: Dictionary<string, HashSet<string>> in C#, Map<String, Set<String>> with HashSet in Java, a dict of sets in Python, and a Map of Sets in JavaScript and TypeScript. Adding a friendship becomes Add, add or add on both people's sets, and "are Dev and Fay friends?" becomes one lookup, Contains, contains, in or has, O(1) on average. Today's social apps keep their friendships this way, or in a database that does the same job.

Which one to choose

Start from the size and the job. Most real graphs are sparse: each vertex is joined to only a few of the others, as with roads, friendships and links. For those, the adjacency list is the usual choice, with sets when pair checks are common.

A grid earns its space when the graph is small, such as the mileage chart for 50 cities (2,500 boxes), or dense, with most pairs joined, or when checking pairs is almost the only job and the vertices never change. Adding a vertex to a grid means redrawing it one row and one column bigger.

Cost card

V is the number of vertices, E the number of edges, and k how many neighbors one vertex has.

What you do Adjacency list Adjacency list of sets Adjacency matrix The everyday reason
Memory O(V + E) O(V + E) O(V²) A page per person with only their friends, versus a box for every possible pair
Check whether two are joined O(k) O(1) on average O(1) Read down one page, look it up in a set, or look in one box
List a vertex's neighbors O(k) O(k) O(V) Read one page, versus check every box in a row
Add an edge O(1) O(1) on average O(1) A note on two pages, versus marking two boxes
Add a vertex O(1) O(1) O(V²) A new page, versus redrawing the whole grid one row and one column bigger

Check yourself

2 questions to try on the lesson page.

So what

When you build anything with a graph inside, from a map to an Add friend button, pick its storage from the job it does most: a page per person for the usual sparse graph, with sets when you check pairs, and a grid only when the graph is small or dense.

Key terms

Cheat sheets

Related