Representing Graphs

Every data structure so far in this course has had a fairly rigid shape. A tree has one parent per child, a linked list is a single chain. A graph drops that rigidity entirely: it is just a set of nodes (also called vertices) and a set of edges connecting pairs of them, with no restriction on how many connections a node can have or what shape the overall structure takes. Graphs are how you model anything that is fundamentally a network, cities and roads, people and friendships, servers and network links, tasks and their dependencies.

• -Directed vs undirected: a directed edge only allows travel one way (a one-way street, a "follows" relationship). An undirected edge allows travel both ways (a two-way road, a mutual friendship).
• -Weighted vs unweighted: a weighted edge carries a cost, distance, or time. An unweighted edge just represents "connected" or "not connected," with every edge implicitly costing the same.
• -A path is a sequence of edges connecting one node to another. A cycle is a path that returns to where it started.

An adjacency list represents a graph as a dictionary (or array) mapping each node to a list of its neighbors. For a weighted graph, each entry in that list pairs a neighbor with the edge's weight.

An adjacency matrix instead represents a graph as an n x n grid, where matrix[i][j] holds the edge weight (or just 1/0 for unweighted) between node i and node j.

An adjacency matrix always takes O(n²) space, no matter how few edges the graph actually has, and checking "are these two nodes connected" is O(1). An adjacency list instead takes O(n + e) space, where e is the actual number of edges, and most real-world graphs (road networks, social graphs, service dependency graphs) are sparse, meaning e is much closer to n than to n². For those graphs, an adjacency list uses dramatically less memory, and the operation every graph algorithm in this module actually needs, "give me all of this node's neighbors," is just as fast with a list as with a matrix row. The matrix only wins when the graph is dense (close to every possible edge existing) or when O(1) "are u and v directly connected" lookups dominate the workload.

• -Adjacency list: O(n + e) space, fast to enumerate a node's neighbors, the default choice for sparse graphs (almost every real-world graph).
• -Adjacency matrix: O(n²) space regardless of edge count, O(1) direct-connection lookup, worth it only for dense graphs or when that specific lookup pattern dominates.
• -Every algorithm in the rest of this module, BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, topological sort, is written against the adjacency-list shape shown above.