Loading...
Graphs, traversal, and shortest paths
Section 1 of 4
Learn the basic concepts, terminology, and representations of graphs
Edges have no direction - connections go both ways
A fundamental unit that represents an entity in the graph.
A connection between two vertices, representing a relationship.
The number of edges connected to a vertex.
A sequence of vertices connected by edges.
A path that starts and ends at the same vertex.
A graph where every vertex is reachable from every other vertex.
A graph formed from a subset of vertices and edges.
A graph where every vertex is connected to every other vertex.
A 2D array where entry (i,j) indicates if there's an edge between vertex i and j.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
An array of lists where each vertex stores a list of its adjacent vertices.
| Aspect | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space Complexity | O(V²) | O(V + E) |
| Edge Lookup | O(1) | O(degree) |
| Add/Remove Edge | O(1) | O(1) / O(degree) |
| Best for | Dense graphs | Sparse graphs |
People as vertices, friendships as edges. Used for friend recommendations and community detection.
Devices as vertices, connections as edges. Essential for routing and network topology design.
Cities as vertices, roads/flights as edges. Powers GPS navigation and route optimization.
In a social network with 1000 users where each user has an average of 150 friends, which representation would be more memory efficient?
Correct! The adjacency list uses O(V + E) = O(1000 + 150,000) space, much less than the matrix's O(V²) = O(1,000,000) space.