Part VI — Graph Structures

Graphs are the most versatile data structure in computer science. Every time you model a social network, a road map, a dependency chain, or a recommendation engine, you are working with a graph. Trees, linked lists, and even arrays are special cases of graphs with additional constraints. Mastering graphs unlocks an entire category of interview problems that intimidate candidates who never invested the time to learn the fundamentals.

This section gives you the vocabulary, the representation strategies, and the algorithmic toolkit to solve graph problems with confidence.

Core Terminology

A graph G = (V, E) consists of a set of vertices (also called nodes) and a set of edges (connections between vertices). Every graph problem reduces to reasoning about vertices and the relationships between them.

Vertex (Node): A discrete entity in the graph. In a social network, each user is a vertex. In a road map, each intersection is a vertex.

Edge: A connection between two vertices. In a social network, a friendship is an edge. In a road map, a road segment is an edge.

Degree: The number of edges incident to a vertex. In a directed graph, this splits into in-degree (edges pointing to the vertex) and out-degree (edges pointing away from the vertex). The sum of all degrees in an undirected graph equals twice the number of edges — every edge contributes to two vertices.

Path: A sequence of vertices where each consecutive pair is connected by an edge. A simple path visits no vertex more than once.

Cycle: A path that starts and ends at the same vertex with no repeated edges. A graph with no cycles is acyclic. A directed acyclic graph (DAG) is one of the most useful structures in all of computer science — it models everything from build systems to course prerequisites.

Connected Component: A maximal set of vertices such that every pair has a path between them. In a social network, each connected component is an isolated community with no cross-links.

DAG (Directed Acyclic Graph): A directed graph with no cycles. DAGs support topological sorting — a linear ordering of vertices where every edge points forward. Build tools like Maven and Gradle rely on topological sort to determine compilation order.

Directed vs. Undirected

An undirected graph treats edges as bidirectional. If Alice is friends with Bob, Bob is friends with Alice. Each edge {u, v} implies traversal in both directions.

A directed graph (digraph) assigns a direction to each edge. Following someone on Twitter is directed — you follow them, but they do not necessarily follow you back. Each edge (u, v) allows traversal only from u to v.

The distinction affects every algorithm. Cycle detection, shortest paths, and connectivity all behave differently depending on whether edges carry direction.

Weighted vs. Unweighted

An unweighted graph treats all edges as equal. The “cost” of traversing any edge is 1. BFS finds shortest paths in unweighted graphs because it explores level by level.

A weighted graph assigns a numeric weight to each edge. Road distances, latency between servers, and costs in a supply chain all require weighted edges. Shortest path algorithms like Dijkstra’s and Bellman-Ford exist because BFS alone cannot handle variable edge weights.

Negative weights introduce additional complexity. Dijkstra’s algorithm fails on negative weights, while Bellman-Ford handles them at the cost of higher time complexity.

Adjacency Matrix vs. Adjacency List

Two representations dominate graph implementations. Choosing the right one depends on the graph’s density and the operations you need.

Adjacency Matrix

Store a 2D array matrix[V][V] where matrix[u][v] holds the edge weight (or true/false for unweighted graphs). Checking whether an edge exists between two vertices takes O(1) time — a direct array lookup.

The cost is space: O(V²) regardless of how many edges exist. A graph with 10,000 vertices and 20,000 edges wastes the vast majority of a 100-million-element matrix. Adjacency matrices shine when the graph is dense (E approaches V²) or when you need constant-time edge lookups.

Adjacency List

Store a list of neighbors for each vertex. A Map<Integer, List<Edge>> or an array of lists gives O(degree) time to iterate over a vertex’s neighbors and O(V + E) total space — proportional to the actual graph size.

For sparse graphs — and most real-world graphs are sparse — adjacency lists use dramatically less memory and iterate over neighbors faster because they skip non-existent edges.

Comparison Table

Operation	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Check edge (u, v)	O(1)	O(degree(u))
All neighbors of u	O(V)	O(degree(u))
Add edge	O(1)	O(1)
Remove edge	O(1)	O(degree(u))
Add vertex	O(V²) — resize	O(1)
Best for	Dense graphs	Sparse graphs

Interview default: Use an adjacency list unless the problem explicitly requires constant-time edge lookup or the graph is dense. Interviewers expect adjacency lists because they reflect how production systems model graphs.

What’s Ahead

This section covers two chapters that build on this foundation:

Graphs (CH6-S1) — Adjacency list and matrix implementations in Java 25, graph traversals, topological sort with Kahn’s and DFS approaches, cycle detection in both directed and undirected graphs, connected components, bipartite checking, and classic problems like Course Schedule, Clone Graph, and Number of Islands.

Minimum Spanning Trees (CH6-S2) — Kruskal’s algorithm with Union-Find, Prim’s algorithm with priority queues, the cut property, MST applications in network design and clustering, and problems like Min Cost to Connect All Points.

Each chapter delivers production-quality Java 25 code, complexity analysis, edge case handling, and interviewer tips. By the end of this section, graph problems will feel like familiar territory rather than an unpredictable threat.