Introduction to Graphs
Editorial
Every friend of every student
A school keeps track of who's friends with whom: 4,000 students and 20,000 friendships. The first table anyone draws for that has a row and a column for every student and a mark where two of them are friends. Most questions about the school (which friendships stay inside one class, who's a friend of a friend, whether everyone is connected) start the same way: for each student, go through their friends. Here's that loop through the table, and through a list of each student's friends, on the same school in every language. A student's class is their number mod 40:
import time
x = 11 # the same school in every language
def next_number():
global x
x = x * 48271 % 2147483647
return x
n, m = 4000, 20000 # student s sits in class s % 40
matrix = [bytearray(n) for _ in range(n)] # n × n cells: 1 where two students are friends
lists = [[] for _ in range(n)] # each student's friends, and nobody else
added = 0
while added < m:
u, v = next_number() % n, next_number() % n
if u == v or matrix[u][v]: # nobody befriends themselves, and no friendship twice
continue
matrix[u][v] = matrix[v][u] = 1
lists[u].append(v)
lists[v].append(u)
added += 1
print(n, "students,", added, "friendships")
start = time.perf_counter()
pairs_matrix, cells = 0, 0
for u in range(n):
row = matrix[u]
for v in range(n): # the whole row: n cells, friend or not
cells += 1
if row[v] and u < v and u % 40 == v % 40:
pairs_matrix += 1
matrix_ms = round((time.perf_counter() - start) * 1000)
start = time.perf_counter()
pairs_lists, entries = 0, 0
for u in range(n):
for v in lists[u]: # only u's friends
entries += 1
if u < v and u % 40 == v % 40:
pairs_lists += 1
lists_ms = round((time.perf_counter() - start) * 1000)
print("friendships inside a class:", pairs_matrix, "by the matrix,", pairs_lists, "by the lists")
print("read:", cells, "matrix cells |", entries, "list entries")
print(f"matrix: {matrix_ms} ms | lists: {lists_ms} ms")
print("a matrix for 100000 students:", 100000 * 100000, "cells")
# 4000 students, 20000 friendships
# friendships inside a class: 483 by the matrix, 483 by the lists
# read: 16000000 matrix cells | 40000 list entries
# matrix: 2289 ms | lists: 8 ms
# a matrix for 100000 students: 10000000000 cellsimport java.util.*;
public class Main {
static long x = 11; // the same school in every language
static int nextNumber() {
x = x * 48271 % 2147483647;
return (int) x;
}
public static void main(String[] args) {
int n = 4000, m = 20000; // student s sits in class s % 40
boolean[][] matrix = new boolean[n][n]; // n × n cells: true where two students are friends
List<List<Integer>> lists = new ArrayList<>(); // each student's friends, and nobody else
for (int i = 0; i < n; i++) lists.add(new ArrayList<>());
int added = 0;
while (added < m) {
int u = nextNumber() % n, v = nextNumber() % n;
if (u == v || matrix[u][v]) continue; // nobody befriends themselves, and no friendship twice
matrix[u][v] = matrix[v][u] = true;
lists.get(u).add(v);
lists.get(v).add(u);
added++;
}
System.out.println(n + " students, " + added + " friendships");
long start = System.nanoTime();
int pairsMatrix = 0;
long cells = 0;
for (int u = 0; u < n; u++) {
boolean[] row = matrix[u];
for (int v = 0; v < n; v++) { // the whole row: n cells, friend or not
cells++;
if (row[v] && u < v && u % 40 == v % 40) pairsMatrix++;
}
}
long matrixMs = (System.nanoTime() - start) / 1000000;
start = System.nanoTime();
int pairsLists = 0;
long entries = 0;
for (int u = 0; u < n; u++) {
for (int v : lists.get(u)) { // only u's friends
entries++;
if (u < v && u % 40 == v % 40) pairsLists++;
}
}
long listsMs = (System.nanoTime() - start) / 1000000;
System.out.println("friendships inside a class: " + pairsMatrix + " by the matrix, " + pairsLists
+ " by the lists");
System.out.println("read: " + cells + " matrix cells | " + entries + " list entries");
System.out.println("matrix: " + matrixMs + " ms | lists: " + listsMs + " ms");
System.out.println("a matrix for 100000 students: " + 100000L * 100000L + " cells");
}
}
// 4000 students, 20000 friendships
// friendships inside a class: 483 by the matrix, 483 by the lists
// read: 16000000 matrix cells | 40000 list entries
// matrix: 43 ms | lists: 8 ms
// a matrix for 100000 students: 10000000000 cells#include <bits/stdc++.h>
using namespace std;
long long x = 11; // the same school in every language
int nextNumber() {
x = x * 48271 % 2147483647;
return (int) x;
}
long long msSince(chrono::steady_clock::time_point start) {
return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
}
int main() {
int n = 4000, m = 20000; // student s sits in class s % 40
vector<vector<char>> matrix(n, vector<char>(n, 0)); // n × n cells: 1 where two students are friends
vector<vector<int>> lists(n); // each student's friends, and nobody else
int added = 0;
while (added < m) {
int u = nextNumber() % n, v = nextNumber() % n;
if (u == v || matrix[u][v]) continue; // nobody befriends themselves, and no friendship twice
matrix[u][v] = matrix[v][u] = 1;
lists[u].push_back(v);
lists[v].push_back(u);
added++;
}
cout << n << " students, " << added << " friendships\n";
auto start = chrono::steady_clock::now();
int pairsMatrix = 0;
long long cells = 0;
for (int u = 0; u < n; u++) {
const vector<char>& row = matrix[u];
for (int v = 0; v < n; v++) { // the whole row: n cells, friend or not
cells++;
if (row[v] && u < v && u % 40 == v % 40) pairsMatrix++;
}
}
long long matrixMs = msSince(start);
start = chrono::steady_clock::now();
int pairsLists = 0;
long long entries = 0;
for (int u = 0; u < n; u++) {
for (int v : lists[u]) { // only u's friends
entries++;
if (u < v && u % 40 == v % 40) pairsLists++;
}
}
long long listsMs = msSince(start);
cout << "friendships inside a class: " << pairsMatrix << " by the matrix, " << pairsLists << " by the lists\n";
cout << "read: " << cells << " matrix cells | " << entries << " list entries\n";
cout << "matrix: " << matrixMs << " ms | lists: " << listsMs << " ms\n";
cout << "a matrix for 100000 students: " << 100000LL * 100000LL << " cells\n";
}
// 4000 students, 20000 friendships
// friendships inside a class: 483 by the matrix, 483 by the lists
// read: 16000000 matrix cells | 40000 list entries
// matrix: 19 ms | lists: 0 ms
// a matrix for 100000 students: 10000000000 cellslet x = 11; // the same school in every language
function nextNumber() {
x = x * 48271 % 2147483647;
return x;
}
const n = 4000, m = 20000; // student s sits in class s % 40
const matrix = Array.from({ length: n }, () => new Uint8Array(n)); // n × n cells: 1 where two students are friends
const lists = Array.from({ length: n }, () => []); // each student's friends, and nobody else
let added = 0;
while (added < m) {
const u = nextNumber() % n, v = nextNumber() % n;
if (u === v || matrix[u][v]) continue; // nobody befriends themselves, and no friendship twice
matrix[u][v] = matrix[v][u] = 1;
lists[u].push(v);
lists[v].push(u);
added++;
}
console.log(`${n} students, ${added} friendships`);
let start = performance.now();
let pairsMatrix = 0, cells = 0;
for (let u = 0; u < n; u++) {
const row = matrix[u];
for (let v = 0; v < n; v++) { // the whole row: n cells, friend or not
cells++;
if (row[v] && u < v && u % 40 === v % 40) pairsMatrix++;
}
}
const matrixMs = Math.round(performance.now() - start);
start = performance.now();
let pairsLists = 0, entries = 0;
for (let u = 0; u < n; u++) {
for (const v of lists[u]) { // only u's friends
entries++;
if (u < v && u % 40 === v % 40) pairsLists++;
}
}
const listsMs = Math.round(performance.now() - start);
console.log(`friendships inside a class: ${pairsMatrix} by the matrix, ${pairsLists} by the lists`);
console.log(`read: ${cells} matrix cells | ${entries} list entries`);
console.log(`matrix: ${matrixMs} ms | lists: ${listsMs} ms`);
console.log(`a matrix for 100000 students: ${100000 * 100000} cells`);
// 4000 students, 20000 friendships
// friendships inside a class: 483 by the matrix, 483 by the lists
// read: 16000000 matrix cells | 40000 list entries
// matrix: 29 ms | lists: 5 ms
// a matrix for 100000 students: 10000000000 cellslet x = 11; // the same school in every language
function nextNumber(): number {
x = x * 48271 % 2147483647;
return x;
}
const n = 4000, m = 20000; // student s sits in class s % 40
const matrix: Uint8Array[] = Array.from({ length: n }, () => new Uint8Array(n)); // 1 where two are friends
const lists: number[][] = Array.from({ length: n }, () => []); // each student's friends only
let added = 0;
while (added < m) {
const u = nextNumber() % n, v = nextNumber() % n;
if (u === v || matrix[u][v]) continue; // nobody befriends themselves, and no friendship twice
matrix[u][v] = matrix[v][u] = 1;
lists[u].push(v);
lists[v].push(u);
added++;
}
console.log(`${n} students, ${added} friendships`);
let start = performance.now();
let pairsMatrix = 0, cells = 0;
for (let u = 0; u < n; u++) {
const row = matrix[u];
for (let v = 0; v < n; v++) { // the whole row: n cells, friend or not
cells++;
if (row[v] && u < v && u % 40 === v % 40) pairsMatrix++;
}
}
const matrixMs = Math.round(performance.now() - start);
start = performance.now();
let pairsLists = 0, entries = 0;
for (let u = 0; u < n; u++) {
for (const v of lists[u]) { // only u's friends
entries++;
if (u < v && u % 40 === v % 40) pairsLists++;
}
}
const listsMs = Math.round(performance.now() - start);
console.log(`friendships inside a class: ${pairsMatrix} by the matrix, ${pairsLists} by the lists`);
console.log(`read: ${cells} matrix cells | ${entries} list entries`);
console.log(`matrix: ${matrixMs} ms | lists: ${listsMs} ms`);
console.log(`a matrix for 100000 students: ${100000 * 100000} cells`);
// 4000 students, 20000 friendships
// friendships inside a class: 483 by the matrix, 483 by the lists
// read: 16000000 matrix cells | 40000 list entries
// matrix: 29 ms | lists: 5 ms
// a matrix for 100000 students: 10000000000 cellsusing System;
using System.Collections.Generic;
using System.Diagnostics;
class Program {
static long x = 11; // the same school in every language
static int NextNumber() {
x = x * 48271 % 2147483647;
return (int) x;
}
static void Main() {
int n = 4000, m = 20000; // student s sits in class s % 40
var matrix = new bool[n][]; // n × n cells: true where two students are friends
var lists = new List<int>[n]; // each student's friends, and nobody else
for (int i = 0; i < n; i++) {
matrix[i] = new bool[n];
lists[i] = new List<int>();
}
int added = 0;
while (added < m) {
int u = NextNumber() % n, v = NextNumber() % n;
if (u == v || matrix[u][v]) continue; // nobody befriends themselves, and no friendship twice
matrix[u][v] = matrix[v][u] = true;
lists[u].Add(v);
lists[v].Add(u);
added++;
}
Console.WriteLine($"{n} students, {added} friendships");
var watch = Stopwatch.StartNew();
int pairsMatrix = 0;
long cells = 0;
for (int u = 0; u < n; u++) {
bool[] row = matrix[u];
for (int v = 0; v < n; v++) { // the whole row: n cells, friend or not
cells++;
if (row[v] && u < v && u % 40 == v % 40) pairsMatrix++;
}
}
long matrixMs = watch.ElapsedMilliseconds;
watch.Restart();
int pairsLists = 0;
long entries = 0;
for (int u = 0; u < n; u++) {
foreach (int v in lists[u]) { // only u's friends
entries++;
if (u < v && u % 40 == v % 40) pairsLists++;
}
}
long listsMs = watch.ElapsedMilliseconds;
Console.WriteLine($"friendships inside a class: {pairsMatrix} by the matrix, {pairsLists} by the lists");
Console.WriteLine($"read: {cells} matrix cells | {entries} list entries");
Console.WriteLine($"matrix: {matrixMs} ms | lists: {listsMs} ms");
Console.WriteLine($"a matrix for 100000 students: {100000L * 100000L} cells");
}
}
// 4000 students, 20000 friendships
// friendships inside a class: 483 by the matrix, 483 by the lists
// read: 16000000 matrix cells | 40000 list entries
// matrix: 11 ms | lists: 0 ms
// a matrix for 100000 students: 10000000000 cellspackage main
import (
"fmt"
"time"
)
var x int64 = 11 // the same school in every language
func nextNumber() int {
x = x * 48271 % 2147483647
return int(x)
}
func main() {
n, m := 4000, 20000 // student s sits in class s % 40
matrix := make([][]bool, n) // n × n cells: true where two students are friends
lists := make([][]int, n) // each student's friends, and nobody else
for i := range matrix {
matrix[i] = make([]bool, n)
}
added := 0
for added < m {
u, v := nextNumber()%n, nextNumber()%n
if u == v || matrix[u][v] { // nobody befriends themselves, and no friendship twice
continue
}
matrix[u][v], matrix[v][u] = true, true
lists[u] = append(lists[u], v)
lists[v] = append(lists[v], u)
added++
}
fmt.Printf("%d students, %d friendships\n", n, added)
start := time.Now()
pairsMatrix, cells := 0, 0
for u := 0; u < n; u++ {
row := matrix[u]
for v := 0; v < n; v++ { // the whole row: n cells, friend or not
cells++
if row[v] && u < v && u%40 == v%40 {
pairsMatrix++
}
}
}
matrixMs := time.Since(start).Milliseconds()
start = time.Now()
pairsLists, entries := 0, 0
for u := 0; u < n; u++ {
for _, v := range lists[u] { // only u's friends
entries++
if u < v && u%40 == v%40 {
pairsLists++
}
}
}
listsMs := time.Since(start).Milliseconds()
fmt.Printf("friendships inside a class: %d by the matrix, %d by the lists\n", pairsMatrix, pairsLists)
fmt.Printf("read: %d matrix cells | %d list entries\n", cells, entries)
fmt.Printf("matrix: %d ms | lists: %d ms\n", matrixMs, listsMs)
fmt.Printf("a matrix for 100000 students: %d cells\n", 100000*100000)
}
// 4000 students, 20000 friendships
// friendships inside a class: 483 by the matrix, 483 by the lists
// read: 16000000 matrix cells | 40000 list entries
// matrix: 16 ms | lists: 0 ms
// a matrix for 100000 students: 10000000000 cellsBoth found the same 483 friendships inside a class, in all seven languages. The table read 16,000,000 cells to find them and the lists read 40,000 entries, 400 times fewer. In Python that was 2,289 ms against 8 ms; in C++, 19 ms against under a millisecond.
The table pays for every pair of students, friends or not: a row has 4,000 cells, and a student here has 10 friends on average. The lists hold the friends and nothing else, each friendship twice, once in each friend's list: 40,000 entries for 20,000 friendships. And the table's size doesn't depend on the friendships at all. For a city's 100,000 students it would be 10,000,000,000 cells before anyone had a single friend.
Vertices, edges and the words around them
That school is a graph: a set of vertices (the students) and a set of edges (the friendships), each edge joining two vertices. These words come up in every graph problem:
| Word | What it means | In the school |
|---|---|---|
| Neighbours | the vertices an edge joins to v | v's friends |
| Degree | how many neighbours v has | how many friends v has |
| Directed edge u → v | an edge that goes one way only | a follow on a social app |
| Weighted edge | an edge with a number on it | the walk in minutes between two homes |
| Path | vertices in a row, each joined to the next | a chain of friends of friends |
| Cycle | a path that ends where it started | three students who are all friends |
| Connected component | the vertices that can all reach each other | a group with no friend outside it |
| Tree | connected, with no cycle: V − 1 edges | a group joined by just enough friendships |
In a directed graph, a vertex has an in-degree (edges coming in) and an out-degree (edges going out). A directed graph with no directed cycle is a DAG: the shape a set of "this must come before that" rules has when all of them can be met.
One fact about degrees explains the lists' size. Every edge of an undirected graph has two ends and adds 1 to the degree of each, so the degrees add up to exactly twice the number of edges. That's why 20,000 friendships made 40,000 list entries. A directed edge u → v is stored once, in u's list, so a directed graph's lists hold exactly E entries.
A graph is sparse when its edges are few for its vertices, like the school's 10 friends each, and dense when they come near V², close to every pair. Most graphs in interviews are sparse.
Three ways to store a graph
Here's a small graph, six vertices and seven edges, stored the three ways: the edge list (the pairs as given), adjacency lists (each vertex's neighbours) and an adjacency matrix (a 6 × 6 table with a 1 where an edge joins two vertices):
n = 6
edges = [(0, 1), (0, 4), (1, 2), (1, 4), (2, 3), (3, 4), (4, 5)] # the edge list: the graph as it's given
lists = [[] for _ in range(n)] # adjacency lists: each vertex's neighbours
matrix = [[0] * n for _ in range(n)] # adjacency matrix: 1 where an edge joins u and v
for u, v in edges:
lists[u].append(v) # undirected: the edge goes in both lists
lists[v].append(u)
matrix[u][v] = 1
matrix[v][u] = 1
print("edge list:", " ".join(f"{u}-{v}" for u, v in edges))
for u in range(n):
print(f"{u}: list {' '.join(map(str, lists[u])):<8} matrix row {' '.join(map(str, matrix[u]))}")
degrees = [len(lists[u]) for u in range(n)]
print("degrees:", " + ".join(map(str, degrees)), "=", sum(degrees), "= 2 x", len(edges), "edges")
# edge list: 0-1 0-4 1-2 1-4 2-3 3-4 4-5
# 0: list 1 4 matrix row 0 1 0 0 1 0
# 1: list 0 2 4 matrix row 1 0 1 0 1 0
# 2: list 1 3 matrix row 0 1 0 1 0 0
# 3: list 2 4 matrix row 0 0 1 0 1 0
# 4: list 0 1 3 5 matrix row 1 1 0 1 0 1
# 5: list 4 matrix row 0 0 0 0 1 0
# degrees: 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 x 7 edgesimport java.util.*;
public class Main {
public static void main(String[] args) {
int n = 6;
int[][] edges = {{0, 1}, {0, 4}, {1, 2}, {1, 4}, {2, 3}, {3, 4}, {4, 5}}; // the graph as it's given
List<List<Integer>> lists = new ArrayList<>(); // adjacency lists: each vertex's neighbours
for (int i = 0; i < n; i++) lists.add(new ArrayList<>());
int[][] matrix = new int[n][n]; // adjacency matrix: 1 where an edge joins u and v
for (int[] e : edges) {
int u = e[0], v = e[1];
lists.get(u).add(v); // undirected: the edge goes in both lists
lists.get(v).add(u);
matrix[u][v] = 1;
matrix[v][u] = 1;
}
StringBuilder given = new StringBuilder("edge list:");
for (int[] e : edges) given.append(" ").append(e[0]).append("-").append(e[1]);
System.out.println(given);
for (int u = 0; u < n; u++) {
StringJoiner list = new StringJoiner(" "), row = new StringJoiner(" ");
for (int v : lists.get(u)) list.add(String.valueOf(v));
for (int cell : matrix[u]) row.add(String.valueOf(cell));
System.out.println(String.format("%d: list %-8s matrix row %s", u, list, row));
}
StringJoiner degrees = new StringJoiner(" + ");
int total = 0;
for (int u = 0; u < n; u++) {
degrees.add(String.valueOf(lists.get(u).size()));
total += lists.get(u).size();
}
System.out.println("degrees: " + degrees + " = " + total + " = 2 x " + edges.length + " edges");
}
}
// edge list: 0-1 0-4 1-2 1-4 2-3 3-4 4-5
// 0: list 1 4 matrix row 0 1 0 0 1 0
// 1: list 0 2 4 matrix row 1 0 1 0 1 0
// 2: list 1 3 matrix row 0 1 0 1 0 0
// 3: list 2 4 matrix row 0 0 1 0 1 0
// 4: list 0 1 3 5 matrix row 1 1 0 1 0 1
// 5: list 4 matrix row 0 0 0 0 1 0
// degrees: 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 x 7 edges#include <bits/stdc++.h>
using namespace std;
string joined(const vector<int>& values, const string& sep) {
string s;
for (size_t i = 0; i < values.size(); i++) s += (i ? sep : "") + to_string(values[i]);
return s;
}
int main() {
int n = 6;
vector<pair<int, int>> edges = {{0, 1}, {0, 4}, {1, 2}, {1, 4}, {2, 3}, {3, 4}, {4, 5}}; // as it's given
vector<vector<int>> lists(n); // adjacency lists: each vertex's neighbours
vector<vector<int>> matrix(n, vector<int>(n, 0)); // adjacency matrix: 1 where an edge joins u and v
for (auto [u, v] : edges) {
lists[u].push_back(v); // undirected: the edge goes in both lists
lists[v].push_back(u);
matrix[u][v] = 1;
matrix[v][u] = 1;
}
cout << "edge list:";
for (auto [u, v] : edges) cout << " " << u << "-" << v;
cout << "\n";
for (int u = 0; u < n; u++) {
string list = joined(lists[u], " ");
list.resize(max<size_t>(list.size(), 8), ' ');
cout << u << ": list " << list << " matrix row " << joined(matrix[u], " ") << "\n";
}
vector<int> degrees;
int total = 0;
for (int u = 0; u < n; u++) {
degrees.push_back(lists[u].size());
total += lists[u].size();
}
cout << "degrees: " << joined(degrees, " + ") << " = " << total << " = 2 x " << edges.size() << " edges\n";
}
// edge list: 0-1 0-4 1-2 1-4 2-3 3-4 4-5
// 0: list 1 4 matrix row 0 1 0 0 1 0
// 1: list 0 2 4 matrix row 1 0 1 0 1 0
// 2: list 1 3 matrix row 0 1 0 1 0 0
// 3: list 2 4 matrix row 0 0 1 0 1 0
// 4: list 0 1 3 5 matrix row 1 1 0 1 0 1
// 5: list 4 matrix row 0 0 0 0 1 0
// degrees: 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 x 7 edgesconst n = 6;
const edges = [[0, 1], [0, 4], [1, 2], [1, 4], [2, 3], [3, 4], [4, 5]]; // the edge list: the graph as it's given
const lists = Array.from({ length: n }, () => []); // adjacency lists: each vertex's neighbours
const matrix = Array.from({ length: n }, () => new Array(n).fill(0)); // adjacency matrix: 1 where an edge joins u, v
for (const [u, v] of edges) {
lists[u].push(v); // undirected: the edge goes in both lists
lists[v].push(u);
matrix[u][v] = 1;
matrix[v][u] = 1;
}
console.log("edge list: " + edges.map(([u, v]) => `${u}-${v}`).join(" "));
for (let u = 0; u < n; u++) {
console.log(`${u}: list ${lists[u].join(" ").padEnd(8)} matrix row ${matrix[u].join(" ")}`);
}
const degrees = lists.map((list) => list.length);
const total = degrees.reduce((a, b) => a + b, 0);
console.log(`degrees: ${degrees.join(" + ")} = ${total} = 2 x ${edges.length} edges`);
// edge list: 0-1 0-4 1-2 1-4 2-3 3-4 4-5
// 0: list 1 4 matrix row 0 1 0 0 1 0
// 1: list 0 2 4 matrix row 1 0 1 0 1 0
// 2: list 1 3 matrix row 0 1 0 1 0 0
// 3: list 2 4 matrix row 0 0 1 0 1 0
// 4: list 0 1 3 5 matrix row 1 1 0 1 0 1
// 5: list 4 matrix row 0 0 0 0 1 0
// degrees: 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 x 7 edgesconst n = 6;
const edges: [number, number][] = [[0, 1], [0, 4], [1, 2], [1, 4], [2, 3], [3, 4], [4, 5]]; // as it's given
const lists: number[][] = Array.from({ length: n }, () => []); // each vertex's neighbours
const matrix: number[][] = Array.from({ length: n }, () => new Array(n).fill(0)); // 1 where an edge joins u and v
for (const [u, v] of edges) {
lists[u].push(v); // undirected: the edge goes in both lists
lists[v].push(u);
matrix[u][v] = 1;
matrix[v][u] = 1;
}
console.log("edge list: " + edges.map(([u, v]) => `${u}-${v}`).join(" "));
for (let u = 0; u < n; u++) {
console.log(`${u}: list ${lists[u].join(" ").padEnd(8)} matrix row ${matrix[u].join(" ")}`);
}
const degrees = lists.map((list) => list.length);
const total = degrees.reduce((a, b) => a + b, 0);
console.log(`degrees: ${degrees.join(" + ")} = ${total} = 2 x ${edges.length} edges`);
// edge list: 0-1 0-4 1-2 1-4 2-3 3-4 4-5
// 0: list 1 4 matrix row 0 1 0 0 1 0
// 1: list 0 2 4 matrix row 1 0 1 0 1 0
// 2: list 1 3 matrix row 0 1 0 1 0 0
// 3: list 2 4 matrix row 0 0 1 0 1 0
// 4: list 0 1 3 5 matrix row 1 1 0 1 0 1
// 5: list 4 matrix row 0 0 0 0 1 0
// degrees: 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 x 7 edgesusing System;
using System.Collections.Generic;
class Program {
static void Main() {
int n = 6;
int[][] edges = { new[] {0, 1}, new[] {0, 4}, new[] {1, 2}, new[] {1, 4}, new[] {2, 3}, new[] {3, 4},
new[] {4, 5} }; // the edge list: the graph as it's given
var lists = new List<int>[n]; // adjacency lists: each vertex's neighbours
for (int i = 0; i < n; i++) lists[i] = new List<int>();
var matrix = new int[n, n]; // adjacency matrix: 1 where an edge joins u and v
foreach (int[] e in edges) {
int u = e[0], v = e[1];
lists[u].Add(v); // undirected: the edge goes in both lists
lists[v].Add(u);
matrix[u, v] = 1;
matrix[v, u] = 1;
}
var given = new List<string>();
foreach (int[] e in edges) given.Add($"{e[0]}-{e[1]}");
Console.WriteLine("edge list: " + string.Join(" ", given));
for (int u = 0; u < n; u++) {
var row = new List<int>();
for (int v = 0; v < n; v++) row.Add(matrix[u, v]);
Console.WriteLine($"{u}: list {string.Join(" ", lists[u]).PadRight(8)} matrix row {string.Join(" ", row)}");
}
var degrees = new List<int>();
int total = 0;
for (int u = 0; u < n; u++) {
degrees.Add(lists[u].Count);
total += lists[u].Count;
}
Console.WriteLine($"degrees: {string.Join(" + ", degrees)} = {total} = 2 x {edges.Length} edges");
}
}
// edge list: 0-1 0-4 1-2 1-4 2-3 3-4 4-5
// 0: list 1 4 matrix row 0 1 0 0 1 0
// 1: list 0 2 4 matrix row 1 0 1 0 1 0
// 2: list 1 3 matrix row 0 1 0 1 0 0
// 3: list 2 4 matrix row 0 0 1 0 1 0
// 4: list 0 1 3 5 matrix row 1 1 0 1 0 1
// 5: list 4 matrix row 0 0 0 0 1 0
// degrees: 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 x 7 edgespackage main
import (
"fmt"
"strconv"
"strings"
)
func joined(values []int, sep string) string {
parts := make([]string, len(values))
for i, v := range values {
parts[i] = strconv.Itoa(v)
}
return strings.Join(parts, sep)
}
func main() {
n := 6
edges := [][2]int{{0, 1}, {0, 4}, {1, 2}, {1, 4}, {2, 3}, {3, 4}, {4, 5}} // the edge list: the graph as it's given
lists := make([][]int, n) // adjacency lists: each vertex's neighbours
matrix := make([][]int, n) // adjacency matrix: 1 where an edge joins u and v
for i := range matrix {
matrix[i] = make([]int, n)
}
for _, e := range edges {
u, v := e[0], e[1]
lists[u] = append(lists[u], v) // undirected: the edge goes in both lists
lists[v] = append(lists[v], u)
matrix[u][v] = 1
matrix[v][u] = 1
}
given := []string{}
for _, e := range edges {
given = append(given, fmt.Sprintf("%d-%d", e[0], e[1]))
}
fmt.Println("edge list: " + strings.Join(given, " "))
for u := 0; u < n; u++ {
fmt.Printf("%d: list %-8s matrix row %s\n", u, joined(lists[u], " "), joined(matrix[u], " "))
}
degrees, total := []int{}, 0
for u := 0; u < n; u++ {
degrees = append(degrees, len(lists[u]))
total += len(lists[u])
}
fmt.Printf("degrees: %s = %d = 2 x %d edges\n", joined(degrees, " + "), total, len(edges))
}
// edge list: 0-1 0-4 1-2 1-4 2-3 3-4 4-5
// 0: list 1 4 matrix row 0 1 0 0 1 0
// 1: list 0 2 4 matrix row 1 0 1 0 1 0
// 2: list 1 3 matrix row 0 1 0 1 0 0
// 3: list 2 4 matrix row 0 0 1 0 1 0
// 4: list 0 1 3 5 matrix row 1 1 0 1 0 1
// 5: list 4 matrix row 0 0 0 0 1 0
// degrees: 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 x 7 edgesThe edge list is what problems usually hand you. The lists hold every edge twice, 14 entries for 7 edges: the degree sum on the last line. The matrix has 36 cells whatever the edges, 14 of them 1, the same on both sides of its diagonal because each edge is stored both ways. What each one costs:
| Stored as | Memory | Is u next to v? | Every neighbour of u |
|---|---|---|---|
| Edge list | O(E) | O(E): read all the pairs | O(E): read all the pairs |
| Adjacency lists | O(V + E) | O(degree of u): scan u's list | O(degree of u) |
| Adjacency matrix | O(V²) | O(1): one cell | O(V): the whole row |
| Lists of hash sets | O(V + E) | O(1) on average | O(degree of u) |
Nearly every graph algorithm spends its time in the last column: for each vertex, every neighbour. On lists that adds up to O(V + E), each list read once and 2E entries in all. On a matrix it's O(V²), every row read in full, which is what the school paid. So adjacency lists are the default.
A matrix earns its V² cells on a small, dense graph, or when the question is "are these two joined?" over and over, as in the all-pairs distances of Weighted Shortest Paths: Dijkstra, Bellman-Ford and Floyd-Warshall. Lists of hash sets get the matrix's one-step lookup at the lists' memory. And the edge list is fine as it is when an algorithm goes through the edges themselves: sorted by weight, as Kruskal's algorithm does in Union-Find and Minimum Spanning Trees, or all of them in rounds, as Bellman-Ford does.
Draw the Adjacency List. Store the lesson's seven edges yourself, tapping each list an edge goes in while the matrix fills, both ways and then one way. Then answer the lesson's questions from the pairs, the lists or the matrix, and watch what each one has to read.
Reading a graph from the input
Problems rarely hand you lists ready-made: you build them from what's given. The first thing to settle is what one pair means. Three shapes come up all the time:
# 1. Course Schedule's pairs: [a, b] means "take b before a", so the edge runs b -> a
n = 3
prerequisites = [[1, 0], [2, 1], [2, 0]]
after = [[] for _ in range(n)]
for a, b in prerequisites:
after[b].append(a) # directed: one list only
print("prerequisites as edges, before -> after:")
for b in range(n):
print(f"{b} -> {' '.join(map(str, after[b])) or '(none)'}")
# 2. Roads with lengths: each list entry carries its weight
roads = [[0, 1, 7], [1, 2, 3], [0, 2, 12]]
weighted = [[] for _ in range(3)]
for u, v, w in roads:
weighted[u].append((v, w)) # undirected: both ends, the same length
weighted[v].append((u, w))
print("roads with their lengths:")
for u in range(3):
print(f"{u}: {' '.join(f'{v} ({w})' for v, w in weighted[u])}")
# 3. Vertices named by strings: a map from name to list
friendships = [["ana", "ben"], ["ben", "cy"], ["dee", "ana"]]
friends = {}
for a, b in friendships:
friends.setdefault(a, []).append(b)
friends.setdefault(b, []).append(a)
print("friends by name:")
for name in sorted(friends):
print(f"{name}: {' '.join(friends[name])}")
# prerequisites as edges, before -> after:
# 0 -> 1 2
# 1 -> 2
# 2 -> (none)
# roads with their lengths:
# 0: 1 (7) 2 (12)
# 1: 0 (7) 2 (3)
# 2: 1 (3) 0 (12)
# friends by name:
# ana: ben dee
# ben: ana cy
# cy: ben
# dee: anaimport java.util.*;
public class Main {
public static void main(String[] args) {
// 1. Course Schedule's pairs: [a, b] means "take b before a", so the edge runs b -> a
int n = 3;
int[][] prerequisites = {{1, 0}, {2, 1}, {2, 0}};
List<List<Integer>> after = new ArrayList<>();
for (int i = 0; i < n; i++) after.add(new ArrayList<>());
for (int[] p : prerequisites) after.get(p[1]).add(p[0]); // directed: one list only
System.out.println("prerequisites as edges, before -> after:");
for (int b = 0; b < n; b++) {
StringJoiner s = new StringJoiner(" ");
for (int a : after.get(b)) s.add(String.valueOf(a));
System.out.println(b + " -> " + (s.length() == 0 ? "(none)" : s.toString()));
}
// 2. Roads with lengths: each list entry carries its weight
int[][] roads = {{0, 1, 7}, {1, 2, 3}, {0, 2, 12}};
List<List<int[]>> weighted = new ArrayList<>();
for (int i = 0; i < 3; i++) weighted.add(new ArrayList<>());
for (int[] r : roads) {
weighted.get(r[0]).add(new int[] {r[1], r[2]}); // undirected: both ends, the same length
weighted.get(r[1]).add(new int[] {r[0], r[2]});
}
System.out.println("roads with their lengths:");
for (int u = 0; u < 3; u++) {
StringJoiner s = new StringJoiner(" ");
for (int[] e : weighted.get(u)) s.add(e[0] + " (" + e[1] + ")");
System.out.println(u + ": " + s);
}
// 3. Vertices named by strings: a map from name to list
String[][] friendships = {{"ana", "ben"}, {"ben", "cy"}, {"dee", "ana"}};
Map<String, List<String>> friends = new TreeMap<>(); // kept sorted by name
for (String[] f : friendships) {
friends.computeIfAbsent(f[0], k -> new ArrayList<>()).add(f[1]);
friends.computeIfAbsent(f[1], k -> new ArrayList<>()).add(f[0]);
}
System.out.println("friends by name:");
for (Map.Entry<String, List<String>> e : friends.entrySet()) {
System.out.println(e.getKey() + ": " + String.join(" ", e.getValue()));
}
}
}
// prerequisites as edges, before -> after:
// 0 -> 1 2
// 1 -> 2
// 2 -> (none)
// roads with their lengths:
// 0: 1 (7) 2 (12)
// 1: 0 (7) 2 (3)
// 2: 1 (3) 0 (12)
// friends by name:
// ana: ben dee
// ben: ana cy
// cy: ben
// dee: ana#include <bits/stdc++.h>
using namespace std;
int main() {
// 1. Course Schedule's pairs: [a, b] means "take b before a", so the edge runs b -> a
int n = 3;
vector<pair<int, int>> prerequisites = {{1, 0}, {2, 1}, {2, 0}};
vector<vector<int>> after(n);
for (auto [a, b] : prerequisites) after[b].push_back(a); // directed: one list only
cout << "prerequisites as edges, before -> after:\n";
for (int b = 0; b < n; b++) {
cout << b << " ->";
if (after[b].empty()) cout << " (none)";
for (int a : after[b]) cout << " " << a;
cout << "\n";
}
// 2. Roads with lengths: each list entry carries its weight
vector<array<int, 3>> roads = {{0, 1, 7}, {1, 2, 3}, {0, 2, 12}};
vector<vector<pair<int, int>>> weighted(3);
for (auto [u, v, w] : roads) {
weighted[u].push_back({v, w}); // undirected: both ends, the same length
weighted[v].push_back({u, w});
}
cout << "roads with their lengths:\n";
for (int u = 0; u < 3; u++) {
cout << u << ":";
for (auto [v, w] : weighted[u]) cout << " " << v << " (" << w << ")";
cout << "\n";
}
// 3. Vertices named by strings: a map from name to list
vector<pair<string, string>> friendships = {{"ana", "ben"}, {"ben", "cy"}, {"dee", "ana"}};
map<string, vector<string>> friends; // kept sorted by name
for (auto& [a, b] : friendships) {
friends[a].push_back(b);
friends[b].push_back(a);
}
cout << "friends by name:\n";
for (auto& [name, list] : friends) {
cout << name << ":";
for (auto& f : list) cout << " " << f;
cout << "\n";
}
}
// prerequisites as edges, before -> after:
// 0 -> 1 2
// 1 -> 2
// 2 -> (none)
// roads with their lengths:
// 0: 1 (7) 2 (12)
// 1: 0 (7) 2 (3)
// 2: 1 (3) 0 (12)
// friends by name:
// ana: ben dee
// ben: ana cy
// cy: ben
// dee: ana// 1. Course Schedule's pairs: [a, b] means "take b before a", so the edge runs b -> a
const n = 3;
const prerequisites = [[1, 0], [2, 1], [2, 0]];
const after = Array.from({ length: n }, () => []);
for (const [a, b] of prerequisites) after[b].push(a); // directed: one list only
console.log("prerequisites as edges, before -> after:");
for (let b = 0; b < n; b++) console.log(`${b} -> ${after[b].join(" ") || "(none)"}`);
// 2. Roads with lengths: each list entry carries its weight
const roads = [[0, 1, 7], [1, 2, 3], [0, 2, 12]];
const weighted = Array.from({ length: 3 }, () => []);
for (const [u, v, w] of roads) {
weighted[u].push([v, w]); // undirected: both ends, the same length
weighted[v].push([u, w]);
}
console.log("roads with their lengths:");
for (let u = 0; u < 3; u++) console.log(`${u}: ${weighted[u].map(([v, w]) => `${v} (${w})`).join(" ")}`);
// 3. Vertices named by strings: a map from name to list
const friendships = [["ana", "ben"], ["ben", "cy"], ["dee", "ana"]];
const friends = new Map();
for (const [a, b] of friendships) {
if (!friends.has(a)) friends.set(a, []);
if (!friends.has(b)) friends.set(b, []);
friends.get(a).push(b);
friends.get(b).push(a);
}
console.log("friends by name:");
for (const name of [...friends.keys()].sort()) console.log(`${name}: ${friends.get(name).join(" ")}`);
// prerequisites as edges, before -> after:
// 0 -> 1 2
// 1 -> 2
// 2 -> (none)
// roads with their lengths:
// 0: 1 (7) 2 (12)
// 1: 0 (7) 2 (3)
// 2: 1 (3) 0 (12)
// friends by name:
// ana: ben dee
// ben: ana cy
// cy: ben
// dee: ana// 1. Course Schedule's pairs: [a, b] means "take b before a", so the edge runs b -> a
const n = 3;
const prerequisites: [number, number][] = [[1, 0], [2, 1], [2, 0]];
const after: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of prerequisites) after[b].push(a); // directed: one list only
console.log("prerequisites as edges, before -> after:");
for (let b = 0; b < n; b++) console.log(`${b} -> ${after[b].join(" ") || "(none)"}`);
// 2. Roads with lengths: each list entry carries its weight
const roads: [number, number, number][] = [[0, 1, 7], [1, 2, 3], [0, 2, 12]];
const weighted: [number, number][][] = Array.from({ length: 3 }, () => []);
for (const [u, v, w] of roads) {
weighted[u].push([v, w]); // undirected: both ends, the same length
weighted[v].push([u, w]);
}
console.log("roads with their lengths:");
for (let u = 0; u < 3; u++) console.log(`${u}: ${weighted[u].map(([v, w]) => `${v} (${w})`).join(" ")}`);
// 3. Vertices named by strings: a map from name to list
const friendships: [string, string][] = [["ana", "ben"], ["ben", "cy"], ["dee", "ana"]];
const friends = new Map<string, string[]>();
for (const [a, b] of friendships) {
if (!friends.has(a)) friends.set(a, []);
if (!friends.has(b)) friends.set(b, []);
friends.get(a)!.push(b);
friends.get(b)!.push(a);
}
console.log("friends by name:");
for (const name of [...friends.keys()].sort()) console.log(`${name}: ${friends.get(name)!.join(" ")}`);
// prerequisites as edges, before -> after:
// 0 -> 1 2
// 1 -> 2
// 2 -> (none)
// roads with their lengths:
// 0: 1 (7) 2 (12)
// 1: 0 (7) 2 (3)
// 2: 1 (3) 0 (12)
// friends by name:
// ana: ben dee
// ben: ana cy
// cy: ben
// dee: anausing System;
using System.Collections.Generic;
class Program {
static void Main() {
// 1. Course Schedule's pairs: [a, b] means "take b before a", so the edge runs b -> a
int n = 3;
int[][] prerequisites = { new[] {1, 0}, new[] {2, 1}, new[] {2, 0} };
var after = new List<int>[n];
for (int i = 0; i < n; i++) after[i] = new List<int>();
foreach (int[] p in prerequisites) after[p[1]].Add(p[0]); // directed: one list only
Console.WriteLine("prerequisites as edges, before -> after:");
for (int b = 0; b < n; b++) {
string shown = after[b].Count == 0 ? "(none)" : string.Join(" ", after[b]);
Console.WriteLine($"{b} -> {shown}");
}
// 2. Roads with lengths: each list entry carries its weight
int[][] roads = { new[] {0, 1, 7}, new[] {1, 2, 3}, new[] {0, 2, 12} };
var weighted = new List<int[]>[3];
for (int i = 0; i < 3; i++) weighted[i] = new List<int[]>();
foreach (int[] r in roads) {
weighted[r[0]].Add(new[] {r[1], r[2]}); // undirected: both ends, the same length
weighted[r[1]].Add(new[] {r[0], r[2]});
}
Console.WriteLine("roads with their lengths:");
for (int u = 0; u < 3; u++) {
var parts = new List<string>();
foreach (int[] e in weighted[u]) parts.Add($"{e[0]} ({e[1]})");
Console.WriteLine($"{u}: {string.Join(" ", parts)}");
}
// 3. Vertices named by strings: a map from name to list
string[][] friendships = { new[] {"ana", "ben"}, new[] {"ben", "cy"}, new[] {"dee", "ana"} };
var friends = new SortedDictionary<string, List<string>>(StringComparer.Ordinal); // kept sorted by name
foreach (string[] f in friendships) {
if (!friends.ContainsKey(f[0])) friends[f[0]] = new List<string>();
if (!friends.ContainsKey(f[1])) friends[f[1]] = new List<string>();
friends[f[0]].Add(f[1]);
friends[f[1]].Add(f[0]);
}
Console.WriteLine("friends by name:");
foreach (var e in friends) Console.WriteLine($"{e.Key}: {string.Join(" ", e.Value)}");
}
}
// prerequisites as edges, before -> after:
// 0 -> 1 2
// 1 -> 2
// 2 -> (none)
// roads with their lengths:
// 0: 1 (7) 2 (12)
// 1: 0 (7) 2 (3)
// 2: 1 (3) 0 (12)
// friends by name:
// ana: ben dee
// ben: ana cy
// cy: ben
// dee: anapackage main
import (
"fmt"
"sort"
"strconv"
"strings"
)
func main() {
// 1. Course Schedule's pairs: [a, b] means "take b before a", so the edge runs b -> a
n := 3
prerequisites := [][2]int{{1, 0}, {2, 1}, {2, 0}}
after := make([][]int, n)
for _, p := range prerequisites {
after[p[1]] = append(after[p[1]], p[0]) // directed: one list only
}
fmt.Println("prerequisites as edges, before -> after:")
for b := 0; b < n; b++ {
parts := []string{}
for _, a := range after[b] {
parts = append(parts, strconv.Itoa(a))
}
if len(parts) == 0 {
parts = append(parts, "(none)")
}
fmt.Printf("%d -> %s\n", b, strings.Join(parts, " "))
}
// 2. Roads with lengths: each list entry carries its weight
roads := [][3]int{{0, 1, 7}, {1, 2, 3}, {0, 2, 12}}
weighted := make([][][2]int, 3)
for _, r := range roads {
weighted[r[0]] = append(weighted[r[0]], [2]int{r[1], r[2]}) // undirected: both ends, the same length
weighted[r[1]] = append(weighted[r[1]], [2]int{r[0], r[2]})
}
fmt.Println("roads with their lengths:")
for u := 0; u < 3; u++ {
parts := []string{}
for _, e := range weighted[u] {
parts = append(parts, fmt.Sprintf("%d (%d)", e[0], e[1]))
}
fmt.Printf("%d: %s\n", u, strings.Join(parts, " "))
}
// 3. Vertices named by strings: a map from name to list
friendships := [][2]string{{"ana", "ben"}, {"ben", "cy"}, {"dee", "ana"}}
friends := map[string][]string{}
for _, f := range friendships {
friends[f[0]] = append(friends[f[0]], f[1])
friends[f[1]] = append(friends[f[1]], f[0])
}
names := []string{}
for name := range friends {
names = append(names, name)
}
sort.Strings(names) // a map keeps no order: sort the names to print them
fmt.Println("friends by name:")
for _, name := range names {
fmt.Printf("%s: %s\n", name, strings.Join(friends[name], " "))
}
}
// prerequisites as edges, before -> after:
// 0 -> 1 2
// 1 -> 2
// 2 -> (none)
// roads with their lengths:
// 0: 1 (7) 2 (12)
// 1: 0 (7) 2 (3)
// 2: 1 (3) 0 (12)
// friends by name:
// ana: ben dee
// ben: ana cy
// cy: ben
// dee: anaA direction stated in words. In Course Schedule, [a, b] means "take b before a", so the edge runs b → a: [1, 0] put 1 in 0's list. Read it the other way round and every dependency points backwards. A directed edge goes in one list only.
Edges with weights. Each list entry carries its number. The road between 0 and 2 is 12 long, and it's in both ends' lists with that length.
Vertices that aren't numbers. People, cities, variable names: a map from name to list does the array's job, and its keys are the vertices. Whether a map keeps an order depends on the language (Go's maps even change theirs from one run to the next), so sort the names when the output needs one. Maps are in Introduction to Hash Tables.
Two more checks before building anything: whether the vertices are numbered from 0 or from 1 (1 to n needs n + 1 lists, or every number shifted down by one), and whether the same edge can appear twice.
A grid is a graph you never build
A grid of cells is a graph too. Every open cell is a vertex, joined to the cells one step up, down, left and right. Nobody stores those edges: a cell's neighbours are worked out when they're needed, from four moves and two checks, that the cell is inside the grid and that it's open:
grid = ["..#.",
".#..",
"...#"]
rows, cols = len(grid), len(grid[0])
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
def neighbours(r, c):
out = []
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == ".": # inside the grid, and open
out.append((nr, nc))
return out
for r, c in [(0, 0), (1, 2), (2, 1)]:
print(f"({r},{c}) ->", " ".join(f"({nr},{nc})" for nr, nc in neighbours(r, c)))
open_cells, ends = 0, 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == ".":
open_cells += 1
ends += len(neighbours(r, c))
print(open_cells, "open cells,", ends // 2, "edges between them, none stored")
print("a full", rows, "x", cols, "grid has", rows * (cols - 1) + cols * (rows - 1), "edges")
# (0,0) -> (1,0) (0,1)
# (1,2) -> (2,2) (1,3)
# (2,1) -> (2,0) (2,2)
# 9 open cells, 8 edges between them, none stored
# a full 3 x 4 grid has 17 edgesimport java.util.*;
public class Main {
static String[] grid = {"..#.",
".#..",
"...#"};
static int rows = grid.length, cols = grid[0].length();
static int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
static List<int[]> neighbours(int r, int c) {
List<int[]> out = new ArrayList<>();
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr].charAt(nc) == '.') { // inside, and open
out.add(new int[] {nr, nc});
}
}
return out;
}
public static void main(String[] args) {
int[][] asked = {{0, 0}, {1, 2}, {2, 1}};
for (int[] cell : asked) {
StringJoiner s = new StringJoiner(" ");
for (int[] nb : neighbours(cell[0], cell[1])) s.add("(" + nb[0] + "," + nb[1] + ")");
System.out.println("(" + cell[0] + "," + cell[1] + ") -> " + s);
}
int open = 0, ends = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r].charAt(c) == '.') {
open++;
ends += neighbours(r, c).size();
}
}
}
System.out.println(open + " open cells, " + ends / 2 + " edges between them, none stored");
System.out.println("a full " + rows + " x " + cols + " grid has " + (rows * (cols - 1) + cols * (rows - 1))
+ " edges");
}
}
// (0,0) -> (1,0) (0,1)
// (1,2) -> (2,2) (1,3)
// (2,1) -> (2,0) (2,2)
// 9 open cells, 8 edges between them, none stored
// a full 3 x 4 grid has 17 edges#include <bits/stdc++.h>
using namespace std;
vector<string> grid = {"..#.",
".#..",
"...#"};
int rows = grid.size(), cols = grid[0].size();
int DIRS[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
vector<pair<int, int>> neighbours(int r, int c) {
vector<pair<int, int>> out;
for (auto& d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '.') { // inside, and open
out.push_back({nr, nc});
}
}
return out;
}
int main() {
vector<pair<int, int>> asked = {{0, 0}, {1, 2}, {2, 1}};
for (auto [r, c] : asked) {
cout << "(" << r << "," << c << ") ->";
for (auto [nr, nc] : neighbours(r, c)) cout << " (" << nr << "," << nc << ")";
cout << "\n";
}
int open = 0, ends = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '.') {
open++;
ends += neighbours(r, c).size();
}
}
}
cout << open << " open cells, " << ends / 2 << " edges between them, none stored\n";
cout << "a full " << rows << " x " << cols << " grid has " << rows * (cols - 1) + cols * (rows - 1) << " edges\n";
}
// (0,0) -> (1,0) (0,1)
// (1,2) -> (2,2) (1,3)
// (2,1) -> (2,0) (2,2)
// 9 open cells, 8 edges between them, none stored
// a full 3 x 4 grid has 17 edgesconst grid = ["..#.",
".#..",
"...#"];
const rows = grid.length, cols = grid[0].length;
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right
function neighbours(r, c) {
const out = [];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === ".") { // inside the grid, and open
out.push([nr, nc]);
}
}
return out;
}
for (const [r, c] of [[0, 0], [1, 2], [2, 1]]) {
console.log(`(${r},${c}) -> ${neighbours(r, c).map(([nr, nc]) => `(${nr},${nc})`).join(" ")}`);
}
let open = 0, ends = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === ".") {
open++;
ends += neighbours(r, c).length;
}
}
}
console.log(`${open} open cells, ${ends / 2} edges between them, none stored`);
console.log(`a full ${rows} x ${cols} grid has ${rows * (cols - 1) + cols * (rows - 1)} edges`);
// (0,0) -> (1,0) (0,1)
// (1,2) -> (2,2) (1,3)
// (2,1) -> (2,0) (2,2)
// 9 open cells, 8 edges between them, none stored
// a full 3 x 4 grid has 17 edgesconst grid: string[] = ["..#.",
".#..",
"...#"];
const rows = grid.length, cols = grid[0].length;
const DIRS: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right
function neighbours(r: number, c: number): [number, number][] {
const out: [number, number][] = [];
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === ".") { // inside the grid, and open
out.push([nr, nc]);
}
}
return out;
}
for (const [r, c] of [[0, 0], [1, 2], [2, 1]]) {
console.log(`(${r},${c}) -> ${neighbours(r, c).map(([nr, nc]) => `(${nr},${nc})`).join(" ")}`);
}
let open = 0, ends = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === ".") {
open++;
ends += neighbours(r, c).length;
}
}
}
console.log(`${open} open cells, ${ends / 2} edges between them, none stored`);
console.log(`a full ${rows} x ${cols} grid has ${rows * (cols - 1) + cols * (rows - 1)} edges`);
// (0,0) -> (1,0) (0,1)
// (1,2) -> (2,2) (1,3)
// (2,1) -> (2,0) (2,2)
// 9 open cells, 8 edges between them, none stored
// a full 3 x 4 grid has 17 edgesusing System;
using System.Collections.Generic;
class Program {
static readonly string[] Grid = {"..#.",
".#..",
"...#"};
static readonly int Rows = Grid.Length, Cols = Grid[0].Length;
static readonly int[][] Dirs = { new[] {-1, 0}, new[] {1, 0}, new[] {0, -1}, new[] {0, 1} }; // up, down, left, right
static List<int[]> Neighbours(int r, int c) {
var found = new List<int[]>();
foreach (int[] d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < Rows && nc >= 0 && nc < Cols && Grid[nr][nc] == '.') { // inside, and open
found.Add(new[] {nr, nc});
}
}
return found;
}
static void Main() {
int[][] asked = { new[] {0, 0}, new[] {1, 2}, new[] {2, 1} };
foreach (int[] cell in asked) {
var parts = new List<string>();
foreach (int[] nb in Neighbours(cell[0], cell[1])) parts.Add($"({nb[0]},{nb[1]})");
Console.WriteLine($"({cell[0]},{cell[1]}) -> {string.Join(" ", parts)}");
}
int open = 0, ends = 0;
for (int r = 0; r < Rows; r++) {
for (int c = 0; c < Cols; c++) {
if (Grid[r][c] == '.') {
open++;
ends += Neighbours(r, c).Count;
}
}
}
Console.WriteLine($"{open} open cells, {ends / 2} edges between them, none stored");
Console.WriteLine($"a full {Rows} x {Cols} grid has {Rows * (Cols - 1) + Cols * (Rows - 1)} edges");
}
}
// (0,0) -> (1,0) (0,1)
// (1,2) -> (2,2) (1,3)
// (2,1) -> (2,0) (2,2)
// 9 open cells, 8 edges between them, none stored
// a full 3 x 4 grid has 17 edgespackage main
import (
"fmt"
"strings"
)
var grid = []string{
"..#.",
".#..",
"...#",
}
var rows, cols = len(grid), len(grid[0])
var dirs = [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // up, down, left, right
func neighbours(r, c int) [][2]int {
out := [][2]int{}
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '.' { // inside the grid, and open
out = append(out, [2]int{nr, nc})
}
}
return out
}
func main() {
for _, cell := range [][2]int{{0, 0}, {1, 2}, {2, 1}} {
parts := []string{}
for _, nb := range neighbours(cell[0], cell[1]) {
parts = append(parts, fmt.Sprintf("(%d,%d)", nb[0], nb[1]))
}
fmt.Printf("(%d,%d) -> %s\n", cell[0], cell[1], strings.Join(parts, " "))
}
open, ends := 0, 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '.' {
open++
ends += len(neighbours(r, c))
}
}
}
fmt.Printf("%d open cells, %d edges between them, none stored\n", open, ends/2)
fmt.Printf("a full %d x %d grid has %d edges\n", rows, cols, rows*(cols-1)+cols*(rows-1))
}
// (0,0) -> (1,0) (0,1)
// (1,2) -> (2,2) (1,3)
// (2,1) -> (2,0) (2,2)
// 9 open cells, 8 edges between them, none stored
// a full 3 x 4 grid has 17 edges(0,0) is a corner, so only two of its four moves stay inside. (1,2) has walls above it and to its left. Nine open cells and eight edges between them, none of them stored. A full 3 × 4 grid has R(C − 1) + C(R − 1) = 17 edges: the sideways ones in each row plus the up-and-down ones in each column. A cell has at most four neighbours, three on a side and two in a corner.
The same goes for any graph whose edges follow a rule. A lock of four dials has 10,000 combinations, each one turn away from eight others; a word is one letter away from other words in a dictionary. Those graphs are searched without ever being written down, in Shortest Paths with BFS.
Copying a graph
Clone Graph hands you one node and asks for a deep copy of its graph: new nodes, joined the same way, sharing nothing with the original. What makes it harder than copying a tree is that a graph can reach a node twice, along two paths or around a cycle. So the copy keeps a map from each original node to its copy. Reaching a node that's already in the map hands back that same copy; reaching a new one makes its copy, puts it in the map, and only then copies its neighbours:
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
def copy_graph(node, copies):
if node in copies: # copied already: hand back that same copy
return copies[node]
copy = Node(node.val)
copies[node] = copy # into the map before the neighbours, so a cycle finds it
for nb in node.neighbors:
copy.neighbors.append(copy_graph(nb, copies))
return copy
def join(a, b):
a.neighbors.append(b)
b.neighbors.append(a)
one, two, three, four = Node(1), Node(2), Node(3), Node(4)
join(one, two) # a triangle of 1, 2 and 3, and 4 hanging off 3
join(two, three)
join(three, one)
join(three, four)
copies = {}
copy_graph(one, copies)
print("copied", len(copies), "nodes")
for original in (one, two, three, four):
copy = copies[original]
print(copy.val, "->", " ".join(str(nb.val) for nb in copy.neighbors))
points_back = any(nb in copies for copy in copies.values() for nb in copy.neighbors)
print("a copy's neighbour is an original node:", str(points_back).lower())
# copied 4 nodes
# 1 -> 2 3
# 2 -> 1 3
# 3 -> 2 1 4
# 4 -> 3
# a copy's neighbour is an original node: falseimport java.util.*;
public class Main {
static class Node {
int val;
List<Node> neighbors = new ArrayList<>();
Node(int val) {
this.val = val;
}
}
static Node copyGraph(Node node, Map<Node, Node> copies) {
if (copies.containsKey(node)) return copies.get(node); // copied already: hand back that same copy
Node copy = new Node(node.val);
copies.put(node, copy); // into the map before the neighbours, so a cycle finds it
for (Node nb : node.neighbors) copy.neighbors.add(copyGraph(nb, copies));
return copy;
}
static void join(Node a, Node b) {
a.neighbors.add(b);
b.neighbors.add(a);
}
public static void main(String[] args) {
Node one = new Node(1), two = new Node(2), three = new Node(3), four = new Node(4);
join(one, two); // a triangle of 1, 2 and 3, and 4 hanging off 3
join(two, three);
join(three, one);
join(three, four);
Map<Node, Node> copies = new HashMap<>();
copyGraph(one, copies);
System.out.println("copied " + copies.size() + " nodes");
for (Node original : new Node[] {one, two, three, four}) {
Node copy = copies.get(original);
StringJoiner s = new StringJoiner(" ");
for (Node nb : copy.neighbors) s.add(String.valueOf(nb.val));
System.out.println(copy.val + " -> " + s);
}
boolean pointsBack = false;
for (Node copy : copies.values()) {
for (Node nb : copy.neighbors) if (copies.containsKey(nb)) pointsBack = true;
}
System.out.println("a copy's neighbour is an original node: " + pointsBack);
}
}
// copied 4 nodes
// 1 -> 2 3
// 2 -> 1 3
// 3 -> 2 1 4
// 4 -> 3
// a copy's neighbour is an original node: false#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
vector<Node*> neighbors;
Node(int val) : val(val) {}
};
Node* copyGraph(Node* node, unordered_map<Node*, Node*>& copies) {
if (copies.count(node)) return copies[node]; // copied already: hand back that same copy
Node* copy = new Node(node->val);
copies[node] = copy; // into the map before the neighbours, so a cycle finds it
for (Node* nb : node->neighbors) copy->neighbors.push_back(copyGraph(nb, copies));
return copy;
}
void join(Node* a, Node* b) {
a->neighbors.push_back(b);
b->neighbors.push_back(a);
}
int main() {
Node *one = new Node(1), *two = new Node(2), *three = new Node(3), *four = new Node(4);
join(one, two); // a triangle of 1, 2 and 3, and 4 hanging off 3
join(two, three);
join(three, one);
join(three, four);
unordered_map<Node*, Node*> copies;
copyGraph(one, copies);
cout << "copied " << copies.size() << " nodes\n";
for (Node* original : {one, two, three, four}) {
Node* copy = copies[original];
cout << copy->val << " ->";
for (Node* nb : copy->neighbors) cout << " " << nb->val;
cout << "\n";
}
bool pointsBack = false;
for (auto& [original, copy] : copies) {
for (Node* nb : copy->neighbors) if (copies.count(nb)) pointsBack = true;
}
cout << "a copy's neighbour is an original node: " << boolalpha << pointsBack << "\n";
}
// copied 4 nodes
// 1 -> 2 3
// 2 -> 1 3
// 3 -> 2 1 4
// 4 -> 3
// a copy's neighbour is an original node: falseclass Node {
constructor(val) {
this.val = val;
this.neighbors = [];
}
}
function copyGraph(node, copies) {
if (copies.has(node)) return copies.get(node); // copied already: hand back that same copy
const copy = new Node(node.val);
copies.set(node, copy); // into the map before the neighbours, so a cycle finds it
for (const nb of node.neighbors) copy.neighbors.push(copyGraph(nb, copies));
return copy;
}
function join(a, b) {
a.neighbors.push(b);
b.neighbors.push(a);
}
const one = new Node(1), two = new Node(2), three = new Node(3), four = new Node(4);
join(one, two); // a triangle of 1, 2 and 3, and 4 hanging off 3
join(two, three);
join(three, one);
join(three, four);
const copies = new Map();
copyGraph(one, copies);
console.log(`copied ${copies.size} nodes`);
for (const original of [one, two, three, four]) {
const copy = copies.get(original);
console.log(`${copy.val} -> ${copy.neighbors.map((nb) => nb.val).join(" ")}`);
}
const pointsBack = [...copies.values()].some((copy) => copy.neighbors.some((nb) => copies.has(nb)));
console.log(`a copy's neighbour is an original node: ${pointsBack}`);
// copied 4 nodes
// 1 -> 2 3
// 2 -> 1 3
// 3 -> 2 1 4
// 4 -> 3
// a copy's neighbour is an original node: falseclass GraphNode {
val: number;
neighbors: GraphNode[] = [];
constructor(val: number) {
this.val = val;
}
}
function copyGraph(node: GraphNode, copies: Map<GraphNode, GraphNode>): GraphNode {
if (copies.has(node)) return copies.get(node)!; // copied already: hand back that same copy
const copy = new GraphNode(node.val);
copies.set(node, copy); // into the map before the neighbours, so a cycle finds it
for (const nb of node.neighbors) copy.neighbors.push(copyGraph(nb, copies));
return copy;
}
function join(a: GraphNode, b: GraphNode): void {
a.neighbors.push(b);
b.neighbors.push(a);
}
const one = new GraphNode(1), two = new GraphNode(2), three = new GraphNode(3), four = new GraphNode(4);
join(one, two); // a triangle of 1, 2 and 3, and 4 hanging off 3
join(two, three);
join(three, one);
join(three, four);
const copies = new Map<GraphNode, GraphNode>();
copyGraph(one, copies);
console.log(`copied ${copies.size} nodes`);
for (const original of [one, two, three, four]) {
const copy = copies.get(original)!;
console.log(`${copy.val} -> ${copy.neighbors.map((nb) => nb.val).join(" ")}`);
}
const pointsBack = [...copies.values()].some((copy) => copy.neighbors.some((nb) => copies.has(nb)));
console.log(`a copy's neighbour is an original node: ${pointsBack}`);
// copied 4 nodes
// 1 -> 2 3
// 2 -> 1 3
// 3 -> 2 1 4
// 4 -> 3
// a copy's neighbour is an original node: falseusing System;
using System.Collections.Generic;
class Node {
public int Val;
public List<Node> Neighbors = new List<Node>();
public Node(int val) {
Val = val;
}
}
class Program {
static Node CopyGraph(Node node, Dictionary<Node, Node> copies) {
if (copies.ContainsKey(node)) return copies[node]; // copied already: hand back that same copy
var copy = new Node(node.Val);
copies[node] = copy; // into the map before the neighbours, so a cycle finds it
foreach (Node nb in node.Neighbors) copy.Neighbors.Add(CopyGraph(nb, copies));
return copy;
}
static void Join(Node a, Node b) {
a.Neighbors.Add(b);
b.Neighbors.Add(a);
}
static void Main() {
Node one = new Node(1), two = new Node(2), three = new Node(3), four = new Node(4);
Join(one, two); // a triangle of 1, 2 and 3, and 4 hanging off 3
Join(two, three);
Join(three, one);
Join(three, four);
var copies = new Dictionary<Node, Node>();
CopyGraph(one, copies);
Console.WriteLine($"copied {copies.Count} nodes");
foreach (Node original in new[] {one, two, three, four}) {
Node copy = copies[original];
var vals = new List<int>();
foreach (Node nb in copy.Neighbors) vals.Add(nb.Val);
Console.WriteLine($"{copy.Val} -> {string.Join(" ", vals)}");
}
bool pointsBack = false;
foreach (Node copy in copies.Values) {
foreach (Node nb in copy.Neighbors) if (copies.ContainsKey(nb)) pointsBack = true;
}
Console.WriteLine($"a copy's neighbour is an original node: {pointsBack.ToString().ToLower()}");
}
}
// copied 4 nodes
// 1 -> 2 3
// 2 -> 1 3
// 3 -> 2 1 4
// 4 -> 3
// a copy's neighbour is an original node: falsepackage main
import (
"fmt"
"strconv"
"strings"
)
type Node struct {
Val int
Neighbors []*Node
}
func copyGraph(node *Node, copies map[*Node]*Node) *Node {
if made, ok := copies[node]; ok { // copied already: hand back that same copy
return made
}
cloned := &Node{Val: node.Val}
copies[node] = cloned // into the map before the neighbours, so a cycle finds it
for _, nb := range node.Neighbors {
cloned.Neighbors = append(cloned.Neighbors, copyGraph(nb, copies))
}
return cloned
}
func join(a, b *Node) {
a.Neighbors = append(a.Neighbors, b)
b.Neighbors = append(b.Neighbors, a)
}
func main() {
one, two, three, four := &Node{Val: 1}, &Node{Val: 2}, &Node{Val: 3}, &Node{Val: 4}
join(one, two) // a triangle of 1, 2 and 3, and 4 hanging off 3
join(two, three)
join(three, one)
join(three, four)
copies := map[*Node]*Node{}
copyGraph(one, copies)
fmt.Printf("copied %d nodes\n", len(copies))
for _, original := range []*Node{one, two, three, four} {
cloned := copies[original]
vals := []string{}
for _, nb := range cloned.Neighbors {
vals = append(vals, strconv.Itoa(nb.Val))
}
fmt.Printf("%d -> %s\n", cloned.Val, strings.Join(vals, " "))
}
pointsBack := false
for _, cloned := range copies {
for _, nb := range cloned.Neighbors {
if _, ok := copies[nb]; ok {
pointsBack = true
}
}
}
fmt.Printf("a copy's neighbour is an original node: %t\n", pointsBack)
}
// copied 4 nodes
// 1 -> 2 3
// 2 -> 1 3
// 3 -> 2 1 4
// 4 -> 3
// a copy's neighbour is an original node: falseFour nodes copied, joined exactly as before, and no copy points back into the original. The order of those two steps is the whole trick. Copying 1 puts its copy in the map and moves on to its first neighbour, 2. 2's first neighbour is 1 again, and the map already hands back 1's copy, though 1 isn't finished yet. 2 moves on to 3, whose neighbours lead back to 2 and 1, both in the map: those edges join the copies that exist, and that closes the triangle. Then 3 leads on to 4. Each node is copied once and each edge followed once from each end: O(V + E). The same walk, done with a stack or a queue instead of calls, is in Depth-First and Breadth-First Search.
Spotting a graph problem
Clues that a problem is a graph:
- Things and the links between them: people and friendships, cities and roads, accounts that share an email, computers and cables.
- "Before" and "after": prerequisites, build steps, letters put in order by a dictionary. Those are directed edges.
- A grid you move around in: islands, mazes, oranges rotting cell by cell.
- The fewest steps from one state to another, where a step follows a rule: a lock's dials, a word changing one letter at a time.
- The words connected, reachable, group, network, cycle, route.
Near misses:
- A tree with child pointers is a graph, but it comes with its own tools: Introduction to Binary Trees.
- A grid you only cross right and down, counting paths or adding up values: that's dynamic programming over the cells, not a search.
- Pairs you only need to count, like how many friends each person has: an array of degrees is enough, and no lists are needed.
Mistakes that look right
Two of these run below in every language. The rest are just as common:
- An undirected edge stored one way. The far end never learns about it.
- A copy with no map. A set of nodes already seen stops it looping, but it makes a fresh node every time a seen node comes up again.
- Course Schedule's pairs read backwards. [a, b] is the edge b → a.
- Vertices numbered from 1 in an array of n lists. Vertex n is out of range.
- A grid neighbour without the bounds check. In Python,
grid[-1]is the last row, so a cell in row 0 quietly gets a neighbour from the bottom of the grid. Java and C# throw an exception, and C++ reads whatever happens to be in memory. - A matrix for a big sparse graph. 100,000 vertices is 10,000,000,000 cells, whatever the edges.
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
def shown(values):
return " ".join(map(str, values)) or "(none)"
edges, n = [(0, 1), (1, 2), (2, 3)], 4
one_way = [[] for _ in range(n)]
both_ways = [[] for _ in range(n)]
for u, v in edges:
one_way[u].append(v) # the bug: v never hears about u
both_ways[u].append(v)
both_ways[v].append(u)
print("one way: neighbours of 2 =", shown(one_way[2]) + ", of 3 =", shown(one_way[3]))
print("both ways: neighbours of 2 =", shown(both_ways[2]) + ", of 3 =", shown(both_ways[3]))
made, stubs = 0, 0
def copy_without_map(node, seen):
global made, stubs
copy = Node(node.val)
made += 1
seen.add(node)
for nb in node.neighbors:
if nb in seen: # the bug: a fresh node, not the copy made before
copy.neighbors.append(Node(nb.val))
made += 1
stubs += 1
else:
copy.neighbors.append(copy_without_map(nb, seen))
return copy
a, b, c = Node(1), Node(2), Node(3)
for x, y in ((a, b), (b, c), (c, a)): # a triangle
x.neighbors.append(y)
y.neighbors.append(x)
copy_without_map(a, set())
print("copying a triangle of 3 with no map made", made, "nodes,", stubs, "of them with no neighbours")
# one way: neighbours of 2 = 3, of 3 = (none)
# both ways: neighbours of 2 = 1 3, of 3 = 2
# copying a triangle of 3 with no map made 7 nodes, 4 of them with no neighboursimport java.util.*;
public class Main {
static class Node {
int val;
List<Node> neighbors = new ArrayList<>();
Node(int val) {
this.val = val;
}
}
static int made = 0, stubs = 0;
static Node copyWithoutMap(Node node, Set<Node> seen) {
Node copy = new Node(node.val);
made++;
seen.add(node);
for (Node nb : node.neighbors) {
if (seen.contains(nb)) { // the bug: a fresh node, not the copy made before
copy.neighbors.add(new Node(nb.val));
made++;
stubs++;
} else {
copy.neighbors.add(copyWithoutMap(nb, seen));
}
}
return copy;
}
static String shown(List<Integer> values) {
StringJoiner s = new StringJoiner(" ");
for (int v : values) s.add(String.valueOf(v));
return s.length() == 0 ? "(none)" : s.toString();
}
public static void main(String[] args) {
int[][] edges = {{0, 1}, {1, 2}, {2, 3}};
int n = 4;
List<List<Integer>> oneWay = new ArrayList<>(), bothWays = new ArrayList<>();
for (int i = 0; i < n; i++) {
oneWay.add(new ArrayList<>());
bothWays.add(new ArrayList<>());
}
for (int[] e : edges) {
oneWay.get(e[0]).add(e[1]); // the bug: v never hears about u
bothWays.get(e[0]).add(e[1]);
bothWays.get(e[1]).add(e[0]);
}
System.out.println("one way: neighbours of 2 = " + shown(oneWay.get(2)) + ", of 3 = " + shown(oneWay.get(3)));
System.out.println("both ways: neighbours of 2 = " + shown(bothWays.get(2)) + ", of 3 = "
+ shown(bothWays.get(3)));
Node a = new Node(1), b = new Node(2), c = new Node(3);
Node[][] triangle = {{a, b}, {b, c}, {c, a}};
for (Node[] e : triangle) {
e[0].neighbors.add(e[1]);
e[1].neighbors.add(e[0]);
}
copyWithoutMap(a, new HashSet<>());
System.out.println("copying a triangle of 3 with no map made " + made + " nodes, " + stubs
+ " of them with no neighbours");
}
}
// one way: neighbours of 2 = 3, of 3 = (none)
// both ways: neighbours of 2 = 1 3, of 3 = 2
// copying a triangle of 3 with no map made 7 nodes, 4 of them with no neighbours#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
vector<Node*> neighbors;
Node(int val) : val(val) {}
};
int made = 0, stubs = 0;
Node* copyWithoutMap(Node* node, unordered_set<Node*>& seen) {
Node* copy = new Node(node->val);
made++;
seen.insert(node);
for (Node* nb : node->neighbors) {
if (seen.count(nb)) { // the bug: a fresh node, not the copy made before
copy->neighbors.push_back(new Node(nb->val));
made++;
stubs++;
} else {
copy->neighbors.push_back(copyWithoutMap(nb, seen));
}
}
return copy;
}
string shown(const vector<int>& values) {
if (values.empty()) return "(none)";
string s;
for (size_t i = 0; i < values.size(); i++) s += (i ? " " : "") + to_string(values[i]);
return s;
}
int main() {
vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 3}};
int n = 4;
vector<vector<int>> oneWay(n), bothWays(n);
for (auto [u, v] : edges) {
oneWay[u].push_back(v); // the bug: v never hears about u
bothWays[u].push_back(v);
bothWays[v].push_back(u);
}
cout << "one way: neighbours of 2 = " << shown(oneWay[2]) << ", of 3 = " << shown(oneWay[3]) << "\n";
cout << "both ways: neighbours of 2 = " << shown(bothWays[2]) << ", of 3 = " << shown(bothWays[3]) << "\n";
Node *a = new Node(1), *b = new Node(2), *c = new Node(3);
vector<pair<Node*, Node*>> triangle = {{a, b}, {b, c}, {c, a}};
for (auto [x, y] : triangle) {
x->neighbors.push_back(y);
y->neighbors.push_back(x);
}
unordered_set<Node*> seen;
copyWithoutMap(a, seen);
cout << "copying a triangle of 3 with no map made " << made << " nodes, " << stubs << " of them with no neighbours\n";
}
// one way: neighbours of 2 = 3, of 3 = (none)
// both ways: neighbours of 2 = 1 3, of 3 = 2
// copying a triangle of 3 with no map made 7 nodes, 4 of them with no neighboursclass Node {
constructor(val) {
this.val = val;
this.neighbors = [];
}
}
const shown = (values) => values.join(" ") || "(none)";
const edges = [[0, 1], [1, 2], [2, 3]], n = 4;
const oneWay = Array.from({ length: n }, () => []);
const bothWays = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
oneWay[u].push(v); // the bug: v never hears about u
bothWays[u].push(v);
bothWays[v].push(u);
}
console.log(`one way: neighbours of 2 = ${shown(oneWay[2])}, of 3 = ${shown(oneWay[3])}`);
console.log(`both ways: neighbours of 2 = ${shown(bothWays[2])}, of 3 = ${shown(bothWays[3])}`);
let made = 0, stubs = 0;
function copyWithoutMap(node, seen) {
const copy = new Node(node.val);
made++;
seen.add(node);
for (const nb of node.neighbors) {
if (seen.has(nb)) { // the bug: a fresh node, not the copy made before
copy.neighbors.push(new Node(nb.val));
made++;
stubs++;
} else {
copy.neighbors.push(copyWithoutMap(nb, seen));
}
}
return copy;
}
const a = new Node(1), b = new Node(2), c = new Node(3);
for (const [x, y] of [[a, b], [b, c], [c, a]]) { // a triangle
x.neighbors.push(y);
y.neighbors.push(x);
}
copyWithoutMap(a, new Set());
console.log(`copying a triangle of 3 with no map made ${made} nodes, ${stubs} of them with no neighbours`);
// one way: neighbours of 2 = 3, of 3 = (none)
// both ways: neighbours of 2 = 1 3, of 3 = 2
// copying a triangle of 3 with no map made 7 nodes, 4 of them with no neighboursclass GraphNode {
val: number;
neighbors: GraphNode[] = [];
constructor(val: number) {
this.val = val;
}
}
const shown = (values: number[]): string => values.join(" ") || "(none)";
const edges: [number, number][] = [[0, 1], [1, 2], [2, 3]], n = 4;
const oneWay: number[][] = Array.from({ length: n }, () => []);
const bothWays: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
oneWay[u].push(v); // the bug: v never hears about u
bothWays[u].push(v);
bothWays[v].push(u);
}
console.log(`one way: neighbours of 2 = ${shown(oneWay[2])}, of 3 = ${shown(oneWay[3])}`);
console.log(`both ways: neighbours of 2 = ${shown(bothWays[2])}, of 3 = ${shown(bothWays[3])}`);
let made = 0, stubs = 0;
function copyWithoutMap(node: GraphNode, seen: Set<GraphNode>): GraphNode {
const copy = new GraphNode(node.val);
made++;
seen.add(node);
for (const nb of node.neighbors) {
if (seen.has(nb)) { // the bug: a fresh node, not the copy made before
copy.neighbors.push(new GraphNode(nb.val));
made++;
stubs++;
} else {
copy.neighbors.push(copyWithoutMap(nb, seen));
}
}
return copy;
}
const a = new GraphNode(1), b = new GraphNode(2), c = new GraphNode(3);
const triangle: [GraphNode, GraphNode][] = [[a, b], [b, c], [c, a]];
for (const [x, y] of triangle) {
x.neighbors.push(y);
y.neighbors.push(x);
}
copyWithoutMap(a, new Set<GraphNode>());
console.log(`copying a triangle of 3 with no map made ${made} nodes, ${stubs} of them with no neighbours`);
// one way: neighbours of 2 = 3, of 3 = (none)
// both ways: neighbours of 2 = 1 3, of 3 = 2
// copying a triangle of 3 with no map made 7 nodes, 4 of them with no neighboursusing System;
using System.Collections.Generic;
class Node {
public int Val;
public List<Node> Neighbors = new List<Node>();
public Node(int val) {
Val = val;
}
}
class Program {
static int made = 0, stubs = 0;
static Node CopyWithoutMap(Node node, HashSet<Node> seen) {
var copy = new Node(node.Val);
made++;
seen.Add(node);
foreach (Node nb in node.Neighbors) {
if (seen.Contains(nb)) { // the bug: a fresh node, not the copy made before
copy.Neighbors.Add(new Node(nb.Val));
made++;
stubs++;
} else {
copy.Neighbors.Add(CopyWithoutMap(nb, seen));
}
}
return copy;
}
static string Shown(List<int> values) {
return values.Count == 0 ? "(none)" : string.Join(" ", values);
}
static void Main() {
int[][] edges = { new[] {0, 1}, new[] {1, 2}, new[] {2, 3} };
int n = 4;
var oneWay = new List<int>[n];
var bothWays = new List<int>[n];
for (int i = 0; i < n; i++) {
oneWay[i] = new List<int>();
bothWays[i] = new List<int>();
}
foreach (int[] e in edges) {
oneWay[e[0]].Add(e[1]); // the bug: v never hears about u
bothWays[e[0]].Add(e[1]);
bothWays[e[1]].Add(e[0]);
}
Console.WriteLine($"one way: neighbours of 2 = {Shown(oneWay[2])}, of 3 = {Shown(oneWay[3])}");
Console.WriteLine($"both ways: neighbours of 2 = {Shown(bothWays[2])}, of 3 = {Shown(bothWays[3])}");
Node a = new Node(1), b = new Node(2), c = new Node(3);
Node[][] triangle = { new[] {a, b}, new[] {b, c}, new[] {c, a} };
foreach (Node[] e in triangle) {
e[0].Neighbors.Add(e[1]);
e[1].Neighbors.Add(e[0]);
}
CopyWithoutMap(a, new HashSet<Node>());
Console.WriteLine($"copying a triangle of 3 with no map made {made} nodes, {stubs} of them with no neighbours");
}
}
// one way: neighbours of 2 = 3, of 3 = (none)
// both ways: neighbours of 2 = 1 3, of 3 = 2
// copying a triangle of 3 with no map made 7 nodes, 4 of them with no neighbourspackage main
import (
"fmt"
"strconv"
"strings"
)
type Node struct {
Val int
Neighbors []*Node
}
var made, stubs = 0, 0
func copyWithoutMap(node *Node, seen map[*Node]bool) *Node {
cloned := &Node{Val: node.Val}
made++
seen[node] = true
for _, nb := range node.Neighbors {
if seen[nb] { // the bug: a fresh node, not the copy made before
cloned.Neighbors = append(cloned.Neighbors, &Node{Val: nb.Val})
made++
stubs++
} else {
cloned.Neighbors = append(cloned.Neighbors, copyWithoutMap(nb, seen))
}
}
return cloned
}
func shown(values []int) string {
if len(values) == 0 {
return "(none)"
}
parts := []string{}
for _, v := range values {
parts = append(parts, strconv.Itoa(v))
}
return strings.Join(parts, " ")
}
func main() {
edges, n := [][2]int{{0, 1}, {1, 2}, {2, 3}}, 4
oneWay, bothWays := make([][]int, n), make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
oneWay[u] = append(oneWay[u], v) // the bug: v never hears about u
bothWays[u] = append(bothWays[u], v)
bothWays[v] = append(bothWays[v], u)
}
fmt.Printf("one way: neighbours of 2 = %s, of 3 = %s\n", shown(oneWay[2]), shown(oneWay[3]))
fmt.Printf("both ways: neighbours of 2 = %s, of 3 = %s\n", shown(bothWays[2]), shown(bothWays[3]))
a, b, c := &Node{Val: 1}, &Node{Val: 2}, &Node{Val: 3}
for _, e := range [][2]*Node{{a, b}, {b, c}, {c, a}} { // a triangle
e[0].Neighbors = append(e[0].Neighbors, e[1])
e[1].Neighbors = append(e[1].Neighbors, e[0])
}
copyWithoutMap(a, map[*Node]bool{})
fmt.Printf("copying a triangle of 3 with no map made %d nodes, %d of them with no neighbours\n", made, stubs)
}
// one way: neighbours of 2 = 3, of 3 = (none)
// both ways: neighbours of 2 = 1 3, of 3 = 2
// copying a triangle of 3 with no map made 7 nodes, 4 of them with no neighboursWith each edge added one way, 2's list holds only 3, and 3's list is empty though 3 is joined to 2. The copy without a map made 7 nodes for a triangle of 3: each time a node came up a second time it got a fresh node with no neighbours, 4 of them, instead of the copy already made.
Check yourself
Quiz
1 / 6Multiple choice
An undirected graph has five vertices, with degrees 3, 3, 2, 2 and 2. How many edges does it have?
Multiple choice
An algorithm asks "is u next to v?" millions of times on a graph of 100,000 vertices and 300,000 edges. Which store fits it best?
Multiple choice
In Course Schedule, prerequisites = [[3, 1]] means you must take course 1 before course 3. Which edge goes in the graph?
Multiple choice
In a 5 × 6 grid with every cell open, how many neighbours does the cell in row 0, column 3 have?
Multiple choice
A graph is copied node by node with a map from each original node to its copy. When does a node's copy have to go into the map?
Multiple choice
An undirected graph has the edges [4, 2], [2, 0] and [0, 4], but the code that builds its lists only does
lists[u].append(v). What does it store as 2's neighbours?Practice
The problems in this group, each mapped to the idea it trains:
- Graph Types & Terminology: the three stores built from one edge list, and their costs.
- Graph Representation (C++): the matrix and the lists from an edge list, directed or not.
- Graph Representation (Java): the same two stores in Java.
- Clone Graph: a deep copy with a map from each original node to its copy.