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