Kinds of graphs

The labels below are not mutually exclusive: a graph can be directed, weighted and acyclic at once. They matter because each one changes which algorithm is correct. Breadth-first search gives shortest paths only when edges are unweighted; Dijkstra's algorithm fails with negative weights; a topological order exists only without cycles; a two-colouring exists only if the graph is bipartite. The first thing to settle in an interview is which of these the problem's graph is.

An undirected graph models a symmetric relation: two people who have met, two cells that touch, two cities joined by a road that runs both ways. A directed graph models one that is not: a dependency, a link from one web page to another, a one-way street. Problems signal direction with words like "depends on", "must come before", "points to", "follows" or "from … to".

In a weighted graph every edge carries a number: a distance, a time, a cost, a capacity, a probability. An unweighted graph is the special case where every edge counts as 1.

Weights can be negative (a rebate, a gain in an exchange cycle), and that one fact rules out Dijkstra's algorithm. A later module explains why and gives the replacement.

A graph with at least one cycle is cyclic; one with none is acyclic. A directed acyclic graph, or DAG, is the shape of every schedule and every build: tasks are nodes, and an edge u → v says u must finish before v starts.

A DAG can look like a tree, but it is not one: the features node has three parents. What it shares with a tree is that you can never come back to where you started, which is exactly what makes an order of execution possible.

A tree is a connected undirected graph with no cycle. Three facts about trees are used constantly: a tree on n nodes has exactly n − 1 edges; there is exactly one path between any two nodes; and removing any edge disconnects it. Any two of "connected", "acyclic" and "n − 1 edges" imply the third, which gives a quick test for whether an edge list describes a tree.

A graph is bipartite if its nodes split into two groups with every edge running between the groups and none inside a group. Assignments are bipartite by nature: analysts and desks, students and projects, jobs and machines.

A graph is bipartite exactly when it has no cycle of odd length, and a two-colouring by breadth-first or depth-first search tests that in linear time. A later module does that, and another finds the largest set of pairings with no analyst or desk used twice.

An undirected graph on n nodes has at most n(n − 1)/2 edges. One near that limit is dense; one with a number of edges close to n is sparse. Road networks, social networks and grids are sparse, and the choice of how to store a graph, covered in the next module, turns on this.

Many interview graphs are never stored at all. In a grid each cell is a node and its neighbours are computed from its coordinates; in a word puzzle each word is a node and its neighbours are the words one letter away. The algorithms are the same; only the function that lists neighbours changes.

Before writing code, say out loud what the nodes are, what the edges are, whether they are directed, and whether they carry weights. Most of the interview is decided there.