Graph Fundamentals

What is this?

This is the vocabulary chapter — the words you need before anything else makes sense. A graph is just dots (called vertices) joined by lines (called edges), like a subway map where stations are dots and tracks are lines. Once you can describe a graph — is it one-way or two-way? do the lines have lengths? does it loop back on itself? — you can pick the right tool for any graph problem.

💡 Fun fact: the word "graph" here has nothing to do with the bar charts you drew in school. It comes from the Latin "graphicus" by way of mathematician James Joseph Sylvester, who in 1878 borrowed the term to describe chemical-molecule diagrams — atoms as dots, bonds as lines.

🔓 The problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: every graph algorithm is really a question about a property — is it acyclic? is it connected? is it weighted? — so the fastest way to solve graph problems is to fluently read those properties off a graph and map each one to the algorithm it implies. This chapter is that vocabulary.

1. The vocabulary

A graph is G = (V, E) — a set of vertices and a set of edges connecting them. Everything below is a property you observe or impose on that pair.

Vertex & edge. A vertex (node) is an entity; an edge is a connection between two of them. An edge may be directed (u → v, one-way) or undirected (u — v, mutual).

Degree. The number of edges touching a vertex. In a directed graph it splits into in-degree (edges arriving) and out-degree (edges leaving).

Path. A sequence of vertices each joined to the next by an edge: A → B → D is a path from A to D.

Cycle. A path that returns to its start. A graph with no cycle is acyclic.

Connected & connected component. An undirected graph is connected if there's a path between every pair of vertices. Otherwise it breaks into connected components — maximal connected blobs.

Tree vs general graph. A tree is a connected, acyclic, undirected graph — it has exactly V − 1 edges and a unique path between any two vertices. Add one more edge and you create a cycle; remove one and it disconnects.

DAG. A Directed Acyclic Graph — directed edges, no directed cycle. The shape of every dependency/scheduling problem; it's exactly the class of graphs you can topologically order.

Dense vs sparse. Dense ≈ E close to its maximum (~V²); sparse ≈ E far below that (often ~V). This single judgement drives your representation choice (matrix vs list).

Weighted. Each edge carries a value — distance, cost, capacity, time. Unweighted graphs treat every edge as cost 1.

2. Where the fundamentals bite in real systems

These aren't textbook labels — each property is a real engineering question:

• Cyclic vs acyclic. A build system, a Terraform plan, a Spark job, an import graph — all must be DAGs. A cycle is a bug: a dependency that can never be satisfied. Detecting it is a production correctness check.
• Connected components. "Which microservices form an isolated island after this network partition?" "Which user accounts belong to the same fraud ring?" — both are component-finding.
• Degree / centrality. A node with huge in-degree is a hot dependency or a single point of failure; out-degree spikes flag fan-out load.
• Dense vs sparse. A road network is sparse (a city touches a handful of neighbours); a fully-meshed cluster is dense. The judgement decides whether an adjacency matrix is affordable.
• Weighted. Latency, bandwidth, and dollar cost are edge weights — shortest-path over them is literally how routing and logistics work.

3. The fundamentals toolkit — property → algorithm

Reading a property tells you which tool to grab:

The meta-skill: classify the graph's properties first, and the algorithm is usually a lookup, not an invention.

4. A 30-second worked example

Classify this graph given its edges: 1→2, 2→3, 3→1, 4→3.

Walk the three questions:

• Directed? Yes — every edge has an arrow.
• Cyclic? Yes — 1 → 2 → 3 → 1 returns to its start. So it is not a DAG, and topological sort is impossible here. (If this were a build graph, that 1-2-3 loop is an unresolvable dependency cycle.)
• Connected? Treating direction loosely (weakly connected), vertex 4 reaches the rest, so all four hang together. But note 4 has in-degree 0 — nothing points to it; it's a pure source.

Conclusion: a directed, cyclic, weakly-connected graph — fix or break the 1-2-3 cycle and it becomes a DAG you could schedule. That four-second classification is exactly what tells you which algorithm is even applicable.

5. Common pitfalls 🚫

• Directed ≠ undirected. "Connected" and "cycle" mean different things with arrows. A → B does not let you walk B → A. Mixing this up corrupts both traversal and cycle logic.
• Tree assumptions on a general graph. A general graph can have cycles and multiple paths, so you must track visited — without it, traversal loops forever. Trees let you skip that; graphs never do.
• Forgetting disconnected components. A single DFS/BFS from one start only covers that node's component. To process the whole graph, loop over all vertices and launch a traversal from each unvisited one.
• 0- vs 1-indexed vertices. Off-by-one between vertex labels and array indices is the silent killer of otherwise-correct code.
• "Acyclic" without checking direction. An undirected graph with a back-edge has a cycle; a directed graph needs a directed cycle (three-colour DFS), not merely a repeated vertex.

6. Key takeaways

1. A graph is V + E, and four properties — directed?, weighted?, cyclic?, connected? — determine everything that follows.
2. Each property maps to an algorithm: acyclic ⇒ topological sort, components ⇒ Union-Find/flood, shortest ⇒ BFS (unweighted) or Dijkstra (weighted). Classify, then pick.
3. A tree is the special case — connected, acyclic, V − 1 edges, unique paths; general graphs have cycles and demand visited tracking.
4. A DAG is the scheduler's graph — directed and acyclic is exactly the class you can topologically order.
5. Dense vs sparse is the judgement that drives representation (matrix vs list); weighted vs unweighted drives shortest-path choice.
6. Spend the first 30 seconds classifying the graph — it tells you which tools are even applicable and prevents applying an algorithm to a graph that violates its assumptions.