Graph Representation

A social network is a graph, a road map is a graph, an `import` graph in your codebase is a graph, and so is the dependency tree of a package manager. The reason graphs feel everywhere is that they are the most general relationship structure: just vertices and edges, with no required root, no acyclic constraint, and no fixed branching factor. **Graphs: Representation Basics** is where you stop drawing them on whiteboards and start storing them in code. This lesson defines the core vocabulary (vertex, edge, degree, path, cycle, directed and undirected, connected and disconnected) and walks through the three canonical representations: an adjacency list backed by a hash map of vertex to neighbors, an adjacency matrix for dense graphs and `O(1)` edge-existence queries, and an edge list for algorithms that just iterate over edges. You will analyze the space and time trade-offs of each so you can pick the right one before writing any traversal logic. In **Hash Map (Dictionary) Basics**, you saw that a hash map maps keys to values in expected `O(1)`; an adjacency list is exactly that, mapping each vertex to its list of neighbors. **Queue & Deque** gave you the FIFO machinery that BFS will run on top of these representations once traversal lessons begin. With a graph stored in memory, the algorithms track is where it comes alive: BFS, DFS, shortest paths, connected components, and the rest of the graph algorithm canon.

Highways have lengths in kilometers, flights have ticket prices in dollars, and network links have latencies in milliseconds. Treating any of those graphs as unweighted throws away the only information that matters for the question you actually care about (the shortest, cheapest, or fastest route), which is exactly the gap a **Weighted Graph** representation closes by attaching a number to every edge. This lesson covers three representations: a weighted adjacency list backed by arrays of `{node, weight}` pairs, a weighted adjacency matrix where `matrix[u][v]` is the edge cost (and infinity for non-edges), and a weighted edge list that stores `(u, v, weight)` triples. You will analyze the space and time trade-offs, see why Dijkstra wants the adjacency list, why Floyd-Warshall wants the matrix, and why Kruskal wants the edge list, and you will represent both directed and undirected weighted graphs correctly in each format. In **Graphs: Representation Basics**, you stored connectivity (whether an edge exists) using the same three shapes; the weighted version simply replaces a boolean or membership check with a numeric value. **Hash Map (Dictionary) Basics** is what makes the adjacency list work: a vertex maps to its neighbor-and-weight list in expected `O(1)`, the same way the unweighted version did. With weights in the picture, the algorithms track unlocks shortest-path and minimum-spanning-tree algorithms that read the weight on every edge during their core inner loop.