Storing an Undirected Edge Only Once

An adjacency list for an undirected graph that stores each edge once, under only one of its ends, loses half of every connection: a vertex no longer lists the neighbours whose edges were stored under the other end. This card covers how the mistake arises, what it does to a graph with five vertices, and the rule that prevents it.

An adjacency list keeps one list per vertex, holding the vertices it is joined to by an edge; an undirected edge has no direction, so each end is a neighbour of the other. The mistake is natural because the input usually names each edge once, as a pair such as A-B, and appending B to the list of A feels like recording the pair. It is how a directed edge, which runs one way only, is stored, so code written for one kind of graph and reused for the other carries it over.

The listing builds the graph with edges A-B, A-C, B-C, B-D, C-E and D-E both ways and lists the neighbours of D in each. It also collects every vertex reachable from D by following list entries, to show what a later search would see.

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "E"), ("D", "E")]
vertices = ["A", "B", "C", "D", "E"]


def build(both_directions):
    adjacency = {vertex: [] for vertex in vertices}
    for u, v in edges:
        adjacency[u].append(v)
        if both_directions:
            adjacency[v].append(u)
    return adjacency


def reachable(adjacency, start):
    seen, waiting = {start}, [start]
    while waiting:
        for neighbour in adjacency[waiting.pop()]:
            if neighbour not in seen:
                seen.add(neighbour)
                waiting.append(neighbour)
    return sorted(seen)


for label, both_directions in (("once", False), ("in both directions", True)):
    adjacency = build(both_directions)
    print(f"each edge stored {label}: {sum(len(n) for n in adjacency.values())} entries")
    for vertex in vertices:
        print(f"  {vertex}: [{', '.join(adjacency[vertex])}]")
    print(f"  neighbours of D: [{', '.join(adjacency['D'])}]")
    print(f"  reachable from D: [{', '.join(reachable(adjacency, 'D'))}]")

each edge stored once: 6 entries
  A: [B, C]
  B: [C, D]
  C: [E]
  D: [E]
  E: []
  neighbours of D: [E]
  reachable from D: [D, E]
each edge stored in both directions: 12 entries
  A: [B, C]
  B: [A, C, D]
  C: [A, B, E]
  D: [B, E]
  E: [C, D]
  neighbours of D: [B, E]
  reachable from D: [A, B, C, D, E]

Stored once, the list of D held only E, because B-D was filed under B, and E's list was empty, because both of its edges were filed elsewhere. Following the entries from D reached D and E and nothing else, although the graph is connected. Stored both ways, D listed B and E and every vertex was reachable.

The count gives the mistake away. An undirected graph with E edges has 2E entries in its adjacency list, one at each end of every edge; this graph has 6 edges and 12 entries, and the broken version had 6.

The fix is the second append, adjacency[v].append(u), on every undirected edge. To spot the mistake, add up the list lengths after a build and compare the total with twice the number of edges, or check that every vertex appears in the list of each of its neighbours.