Last Updated: July 15, 2025
Graph Terminology
| Term | Definition |
|---|---|
| Vertex (V) | Node — a point in the graph |
| Edge (E) | Connection between two vertices |
| Directed | Edge has direction — (u → v) ≠ (v → u) |
| Undirected | Edge is bidirectional — {u, v} = {v, u} |
| Weighted | Edge has cost/distance value |
| Degree | Number of edges connected to vertex (in-degree + out-degree for directed) |
| Path | Sequence of vertices connected by edges |
| Cycle | Path that starts and ends at same vertex |
Representations
| Method | Space | Edge Check | Neighbors |
|---|---|---|---|
| Adjacency List | O(V + E) | O(degree) | O(degree) |
| Adjacency Matrix | O(V²) | O(1) | O(V) |
| Edge List | O(E) | O(E) | O(E) |
BFS vs DFS
| Property | BFS | DFS |
|---|---|---|
| Data Structure | Queue (FIFO) | Stack (LIFO) or recursion |
| Finds | Shortest path (unweighted) | Any path, cycles, components |
| Time | O(V + E) | O(V + E) |
| Use Case | Social distance, web crawling | Topological sort, maze solving |
Dijkstra's Algorithm
InputWeighted graph, source vertex S — non-negative edge weights
Initializedist[S] = 0, all others = ∞. Min-heap with (0, S)
While heap not emptyPop (d, u). For each neighbor v: if d + w(u,v) < dist[v], update and push
TimeO((V+E) log V) with binary heap, O(E + V log V) with Fibonacci heap
Key Graph Types
| Type | Properties |
|---|---|
| Tree | Connected, acyclic — |E| = |V| − 1 |
| DAG | Directed Acyclic Graph — topological ordering exists |
| Complete (Kₙ) | Every pair connected — |E| = n(n−1)/2 |
| Bipartite | Vertices can be split into 2 sets, edges only cross sets |
Pro Tip: Adjacency list beats adjacency matrix for sparse graphs (most real-world graphs). Space: O(V+E) vs O(V²). Use matrix only for dense graphs or when edge-existence checks dominate.