graph
A graph is the data structure for things and the connections between them. The things are called vertices (or nodes) and the connections are called edges. Almost anything relational fits this picture: cities joined by roads, people who are friends, web pages that link to each other, or tasks that depend on one another. Whenever you catch yourself drawing dots and lines between them, you are drawing a graph.
Graphs come in flavors. In an undirected graph an edge between A and B goes both ways (friendship: if A knows B, B knows A). In a directed graph each edge has a direction, an arrow from one vertex to another (a one-way street, or 'A follows B' on social media). Edges can also be weighted, carrying a number such as a distance, cost, or capacity; an unweighted graph just records whether a connection exists. With V vertices and E edges, these counts drive the cost of every graph algorithm.
A graph is more general than a tree: a tree is just a connected graph with no cycles. Graphs may have cycles, disconnected pieces, and many paths between the same two vertices, which is exactly why they model the messy real world so well — and why traversing them carefully (so you never visit the same vertex forever) matters.
// 0 --- 1
// | /
// | /
// 2 -+
// vertices: {0, 1, 2}
// edges: {0-1, 0-2, 1-2}Dots are vertices, lines are edges. This same shape can be stored many ways.
Vertex and node mean the same thing here; edge, link, and arc are also used interchangeably. 'Directed graph' is often shortened to digraph.