1 of 4

Your RightSignal

Data structures · 11 of 111 / 3

Graphs

The concept

What a metro map and your Facebook friends have in common

A graph is a set of things, called vertices or nodes, plus the links between pairs of them, called edges. On a metro map, stations are vertices and the tracks between them are edges.

Edges come in kinds. An undirected edge goes both ways, like a Facebook friendship; a directed one goes one way, like an Instagram follow. A weighted edge carries a number, such as minutes between stations.

A tree is a graph with a root and one path to each node. A general graph has no root and can contain cycles, or loops: Ana knows Ben, Ben knows Cleo, Cleo knows Ana.