Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 24/32

Dots and lines: what a graph is

✕
1/9

Vertices and edges

A graph is a bunch of vertices (dots) joined by edges (lines). It's for anything made of relationships: towns and roads, people and friendships, pages and links, map squares and their neighbors.

The trees from earlier units are a special case: a graph with no cycles where every node has a single parent. A general graph can have cycles, several paths between two points, and disconnected pieces.

A vertex's degree is how many edges touch it. Since every edge touches two vertices, the sum of all degrees is twice the number of edges.

ABCDE
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • B and C have degree 3; A, D and E, degree 2. Compare it with the drawing.
  • The sum is 12, twice the 6 edges.
The whole lesson on one page

Vertices and edges

A graph is a bunch of vertices (dots) joined by edges (lines). It's for anything made of relationships: towns and roads, people and friendships, pages and links, map squares and their neighbors.

The trees from earlier units are a special case: a graph with no cycles where every node has a single parent. A general graph can have cycles, several paths between two points, and disconnected pieces.

A vertex's degree is how many edges touch it. Since every edge touches two vertices, the sum of all degrees is twice the number of edges.

ABCDE
const vertices = ["A", "B", "C", "D", "E"];
const aristas = [["A", "B"], ["A", "C"], ["B", "C"], ["B", "D"], ["C", "E"], ["D", "E"]];

console.log(vertices.length, "vertices,", aristas.length, "edges");

const grado = {};
for (const v of vertices) grado[v] = 0;
for (const [a, b] of aristas) {
  grado[a]++;
  grado[b]++;
}
console.log(grado);

let suma = 0;
for (const v of vertices) suma += grado[v];
console.log("sum of degrees:", suma);
  • B and C have degree 3; A, D and E, degree 2. Compare it with the drawing.
  • The sum is 12, twice the 6 edges.

Adjacency list

A list of edges is fine for storing the graph, but not for asking "who are C's neighbors?" without checking all of them. The most common choice is the adjacency list: each vertex gets an array with its neighbors. In JavaScript, a Map (or an object) from vertex to array.

In an undirected graph each edge is written down twice, once at each end. It takes O(V + E) memory (vertices plus edges), and walking a vertex's neighbors costs however many neighbors it has.

const vertices = ["A", "B", "C", "D", "E"];
const aristas = [["A", "B"], ["A", "C"], ["B", "C"], ["B", "D"], ["C", "E"], ["D", "E"]];

const ady = new Map();
for (const v of vertices) ady.set(v, []);
for (const [a, b] of aristas) {
  ady.get(a).push(b);
  ady.get(b).push(a);   // undirected: both ways
}

console.log(ady);
console.log("neighbors of C:", ady.get("C"));
console.log("are B and E neighbors?", ady.get("B").includes("E"));
  • Each vertex has its array of neighbors; edge A–B shows up in A's and in B's.
  • C's neighbors come straight out: [A, B, E].
  • Asking whether B and E are neighbors means scanning B's list: it's false.

Adjacency matrix

The other way is a V × V matrix: cell [i][j] is 1 if there's an edge between i and j, and 0 if not. Asking whether two vertices are joined costs O(1), but the matrix takes O(V²) even when there are hardly any edges.

Rule of thumb: adjacency list almost always; a matrix when the graph is small or nearly everything is connected to everything.

const vertices = ["A", "B", "C", "D", "E"];
const aristas = [["A", "B"], ["A", "C"], ["B", "C"], ["B", "D"], ["C", "E"], ["D", "E"]];

const indice = {};
vertices.forEach((v, i) => { indice[v] = i; });
const n = vertices.length;
const matriz = Array.from({ length: n }, () => new Array(n).fill(0));

for (const [a, b] of aristas) {
  matriz[indice[a]][indice[b]] = 1;
  matriz[indice[b]][indice[a]] = 1;
}

console.log("  " + vertices.join(" "));
for (let i = 0; i < n; i++) console.log(vertices[i], matriz[i].join(" "));
console.log("B and E?", matriz[indice.B][indice.E] === 1);
  • The matrix is symmetric: in an undirected graph, [i][j] and [j][i] always match.
  • Out of 25 cells, only 12 hold a 1. With a thousand vertices it'd be a million cells, almost all zero.

With arrows and weights

Two variants coming up in the next lessons:

  • Directed: the edge has a direction, like following someone on social media (you follow them; whether they follow you, who knows). It's written down once, at the vertex it leaves from.
  • Weighted: each edge carries a number, like a road's kilometers or a flight's cost. In the adjacency list, each neighbor comes with its weight: [neighbor, weight].

The drawing is directed and weighted.

42158ABCD
const aristas = [["A", "B", 4], ["A", "C", 2], ["C", "B", 1], ["B", "D", 5], ["C", "D", 8]];

const ady = {};
for (const [a, b, peso] of aristas) {
  if (!ady[a]) ady[a] = [];
  if (!ady[b]) ady[b] = [];
  ady[a].push([b, peso]);   // directed: only from a to b
}

console.log(ady);
console.log("from C you can go to:", ady.C.map(([v]) => v));
console.log("from D you can go to:", ady.D.map(([v]) => v));
  • Each neighbor carries its weight: A to B costs 4 and A to C, 2.
  • D has no way out: every arrow points into it and none leaves. In a directed graph, "neighbor" depends on the direction.

Further reading