Unit 05
Graphs
Where a tree forces strict hierarchy, a graph lets any node connect to any other. That flexibility is exactly what's needed to model real networks: roads, friendships, dependencies, the internet itself.
// nodes (vertices) connected by edges, with no single root and no restriction on connections
What it is
A graph is a set of nodes (often called vertices) connected by edges. Edges can be directed (one-way, like a "follows" relationship) or undirected (two-way, like a road), and can optionally carry a weight (like distance or cost). Unlike a tree, a graph can have cycles and no node needs to be the "root."
Why it's useful
- Models real networks directly. Maps, social networks, flight routes, and dependency chains between tasks are all naturally graphs.
- Rich traversal algorithms. Breadth-first search finds the shortest path in unweighted graphs; depth-first search explores as far as possible before backtracking; Dijkstra's algorithm finds shortest paths when edges have weights.
Where it struggles
- Can be memory-heavy. A densely connected graph with many edges can require significant storage, especially with an adjacency matrix representation.
- Cycles complicate traversal. Algorithms must track visited nodes to avoid looping forever.
Time complexity (adjacency list representation)
| Operation | Time |
|---|---|
| Add vertex | O(1) |
| Add edge | O(1) |
| BFS / DFS traversal | O(V + E) |
| Check if edge exists | O(degree of vertex) |