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, topological sort - is written against the adjacency-list shape shown above.