Graph Basics | ReConcept Lab

Hook problem

Imagine a building where rooms are connected by doors. You do not need the shape of every room yet. You need a model that answers one small question: from this room, which rooms can I reach in one step?

Rooms become nodesKeep only rooms and direct doors. Ignore room size, hallway shape, and physical distance for now.

A graph model keeps the direct-connection facts and throws away floorplan details that do not matter yet.

First naive idea

One direct way to help visitors is to write route cards: “Lobby -> Hall -> Lab” or “Cafe -> Hall -> Lab.” For a few trips, that feels clear.

Route cards feel naturalComplete route advice is easy to read for a few trips, but it mixes raw structure with human decisions.

Lobby -> Hall -> Labunchanged

Base advice card

Stairs -> Cafe -> Hall -> Labunchanged

Base advice card

Cafe -> Hall -> Labunchanged

Base advice card

Route cards describe full trips, not reusable local facts.

Where it breaks

Now add one new door from Cafe to Lab. The building fact changed once, but several advice cards need review. Some advice remains valid, some is stale, and the new direct advice is missing.

One new door means advice needs reviewThe deliberate Cafe-Lab variant changes the graph fact. The route cards now need a human audit.

Lobby -> Hall -> Labunchanged

Still valid.

Stairs -> Cafe -> Hall -> Labvalid, review

Still reaches Lab, but now needs review.

Cafe -> Hall -> Labstale

Advice should become Cafe -> Lab.

Cafe -> Labmissing

New direct advice is missing.

Graph fact changed; advice cards now need review.

Route cards are human-maintained advice, not an algorithm. The pain is that full routes mix the stable structure with decisions about how to travel.

The core invention

A graph stores local relationship facts. A node represents one object, an edge represents one direct relationship, and adjacency records the immediate neighbors of a node.

Choose what the model keepsFor this page, keep rooms and direct doors. Reject storing every full route.

Keeprooms, direct doors

Throw awayroom size, hallway bends, decoration

Reject herefull route advice like Cafe -> Hall -> Lab

A graph is a modeling choice, not an inevitable copy of the building.

Interactive visual demo

Neighbor inspector

Select a room to see only the one-step neighbors an algorithm can inspect next.

Selected: Hall

One-step neighbors:LobbyLabCafe

HallLobby, Lab, Cafe

Formal version

A graph is often written as G = (V, E). V is the set of vertices or nodes, and E is the set of edges. In this page, Lobby is a node in V, and Lobby-Hall is an edge in E.

Picture to notationLobby becomes a member of V; the Lobby-Hall door becomes an edge in E.

Notation records the same direct facts as the picture.

Edges can be undirected or directed. An undirected stored edge like ["lobby", "hall"] creates two neighbor facts: Lobby lists Hall, and Hall lists Lobby.

Implementation sketch

Storing complete route advice is brittle:

const routeAdvice = [["cafe", "hall", "lab"]];

An adjacency list stores local facts instead:

const adjacency = {
  lobby: ["hall", "stairs"],
  hall: ["lobby", "lab", "cafe"],
  lab: ["hall"],
  stairs: ["lobby", "cafe"],
  cafe: ["hall", "stairs"]
};

Store local facts, not every tripThe adjacency row for Cafe survives route changes better than a list of full advice cards.

Route advice[["cafe","hall","lab"], ...]

Adjacencycafe: ["hall", "stairs"]

LobbyHall, Stairs

HallLobby, Lab, Cafe

LabHall

StairsLobby, Cafe

CafeHall, Stairs

One stored undirected edge creates two neighbor facts.

Representation invariant

The representation is correct when every direct door appears according to the chosen convention. For an undirected graph, every door appears in both rooms’ adjacency rows.

Adjacency listEach row lists the rooms one direct door away.

LobbyHall, Stairs

HallLobby, Lab, Cafe

LabHall

StairsLobby, Cafe

CafeHall, Stairs

Hall connects directly to Lobby, Lab, and Cafe.

Complexity and tradeoffs

An adjacency list is compact when each node has only a few neighbors. An adjacency matrix is a table lookup: choose a row, choose a column, and read whether a direct edge exists.

Representation comparison

Result: Choose an operation to compare the two representations.

Adjacency list

LobbyHall, Stairs

HallLobby, Lab, Cafe

LabHall

StairsLobby, Cafe

CafeHall, Stairs

Adjacency matrix

Rows are from rooms; columns are to rooms.
	Lobby	Hall	Lab	Stairs	Cafe
Lobby	0	1	0	1	0
Hall	1	0	1	0	1
Lab	0	1	0	0	0
Stairs	1	0	0	0	1
Cafe	0	1	0	1	0

Adjacency matrixRows and columns are lookup labels, not physical positions.

Rows are from rooms; columns are to rooms.
	Lobby	Hall	Lab	Stairs	Cafe
Lobby	0	1	0	1	0
Hall	1	0	1	0	1
Lab	0	1	0	0	0
Stairs	1	0	0	0	1
Cafe	0	1	0	1	0

Cell (Lab, Cafe) is 0 because there is no direct door.

Directed and weighted variants

A directed edge changes only one row. A weighted edge adds a cost label, but it does not change whether two nodes are adjacent.

One-way edgeCafe -> Lab changes only Cafe's row. It does not add Lab -> Cafe.

Direction decides which row gets the neighbor.

Cost labels do not change adjacencyHall and Stairs are both still one neighbor step from Lobby, even with costs 2 and 5.

Weight changes cost, not whether a room is adjacent.

Common confusions

An edge is one direct connection. A path chains edges. A neighbor is one edge away. A reachable node may need several edges.

Four common mix-upsEdge vs path, neighbor vs reachable, directed reversal, and weight vs adjacency.

Edge vs path

Hall-Lab is one edge; Lobby -> Hall -> Lab is a path.

Neighbor vs reachable

Lab is reachable from Lobby, but not adjacent to Lobby.

Directed reversal

Lab -> Hall does not automatically allow Hall -> Lab.

Weight vs adjacency

Lobby-Hall cost 2 and Lobby-Stairs cost 5 are both one neighbor step.

The same fixture keeps the vocabulary grounded.

Connections in the graph

BFS repeats the graph-basics question: from the current node, which adjacent neighbors can be visited next? Dijkstra later keeps nodes, edges, and adjacency, then adds edge costs to choose the cheapest next frontier.

Exercises

Which rooms are one-step neighbors of Lobby?
If Cafe -> Lab is a one-way edge, which adjacency row changes?
What is the matrix cell (Lab, Cafe) in the base fixture?
Is Lobby -> Hall -> Lab one edge or a path?

Graph connections : Graph Basics