Graphs

A graph is a set of nodes (vertices) and edges connecting pairs of them, with no rule about parents. Edges can be undirected (a friendship: both ways) or directed (a follow, a one-way street, 'A depends on B'). Edges can carry a weight: a distance, a price, a time.

A graph can contain cycles: you can leave a node and come back to it. Trees are the special case of a connected graph with no cycles. Once you see data as a graph, a family of questions opens up: is there a path from A to B, what's the shortest one, which nodes are reachable, where are the clusters.

There are two standard ways to store a graph. An adjacency list keeps, for each node, the list of its neighbours. Memory is proportional to nodes plus edges, and visiting all neighbours of a node is fast. An adjacency matrix is an n × n table where cell [a][b] says whether there's an edge (or holds its weight). Checking one specific edge is O(1), but memory is n² whatever the number of edges.

Most real graphs are sparse: each node connects to a few others out of millions. A social network with 10 million users has 10¹⁴ matrix cells, almost all empty. So the adjacency list is the default; the matrix suits small or very dense graphs.

from collections import defaultdict, deque
g = defaultdict(list)          # adjacency list
for a, b in [("A","B"), ("A","C"), ("B","D")]:
    g[a].append(b); g[b].append(a)   # undirected: both ways

def reachable(g, start):        # breadth-first search
    seen, q = {start}, deque([start])
    while q:
        for nb in g[q.popleft()]:
            if nb not in seen:
                seen.add(nb); q.append(nb)
    return seen

use std::collections::{HashMap, HashSet, VecDeque};
let mut g: HashMap<&str, Vec<&str>> = HashMap::new();
for (a, b) in [("A","B"), ("A","C"), ("B","D")] {
    g.entry(a).or_default().push(b);
    g.entry(b).or_default().push(a);
}
let (mut seen, mut q) = (HashSet::from(["A"]), VecDeque::from(["A"]));
while let Some(n) = q.pop_front() {
    for &nb in g.get(n).into_iter().flatten() {
        if seen.insert(nb) { q.push_back(nb); }
    }
}