Graph Theory Basics
Core Concepts
| Term | Definition |
|---|---|
| Vertex (Node) | Fundamental unit of a graph |
| Edge | Connection between two vertices |
| Directed Graph (Digraph) | Edges have direction (A→B ≠ B→A) |
| Undirected Graph | Edges have no direction |
| Weighted Graph | Edges have numeric weights/costs |
| Degree | Number of edges connected to a vertex |
| Path | Sequence of vertices connected by edges |
| Cycle | Path that starts and ends at same vertex |
| Connected Graph | Path exists between every pair of vertices |
| Tree | Connected acyclic undirected graph |
| DAG | Directed Acyclic Graph — no directed cycles |
| Spanning Tree | Tree that connects all vertices |
Algorithm Complexity Reference
BFS — Breadth-First Search
Time: O(V + E)
Space: O(V)
Shortest path in unweighted graphs
DFS — Depth-First Search
Time: O(V + E)
Space: O(V)
Cycle detection, topological sort
Dijkstra's Algorithm
Time: O((V+E) log V)
Space: O(V)
Shortest path, non-negative weights
Bellman-Ford
Time: O(V · E)
Space: O(V)
Handles negative weights
Floyd-Warshall
Time: O(V³)
Space: O(V²)
All-pairs shortest paths
Kruskal's MST
Time: O(E log E)
Space: O(V)
Minimum spanning tree
Prim's MST
Time: O(E log V)
Space: O(V)
Dense graphs preferred
Topological Sort
Time: O(V + E)
Space: O(V)
Ordering of DAG vertices