This lesson's interactive features are locked, please to keep using them
Graph Review
When an algorithm traverses a graph, it typically moves across the edges.
Common Use Cases
| Use Case | Vertex | Edge |
|---|---|---|
| Social Networks | User | Connection |
| Road Maps | Location | Road |
| Networks | Computer | Cable |
| Game Dev | Tile | Path |
| AI Decision | State | Action |
Properties
- Graphs can have any number of vertices.
- An undirected graph can have up to
n(n - 1)/2edges fornvertices. - Vertices can exist without edges but may be disconnected (and thus kinda useless)
- Typically graphs (with the exception of multigraphs) can only have a single edge between two vertices
- Weighted graphs assign values (costs) to edges (we'll cover this in a future course)