Graph Theory Basics
Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. In computer science, graphs are used to represent networks, social connections, maps, and more.
1. Core Components
A graph $G$ consists of two sets:
- Vertices (Nodes): The fundamental units or points ($V$).
- Edges (Links): The lines that connect two vertices ($E$).
2. Types of Graphs
Directed vs. Undirected
- Undirected Graph: Edges have no direction. The connection is mutual (e.g., Facebook friends). $(A, B)$ is the same as $(B, A)$.
- Directed Graph (Digraph): Edges have a direction. The connection goes one way (e.g., Twitter followers). $(A \rightarrow B)$ is distinct from $(B \rightarrow A)$.
Weighted vs. Unweighted
- Unweighted: All edges are equal.
- Weighted: Edges have a value (weight/cost) associated with them (e.g., distance between cities on a map).
Cyclic vs. Acyclic
- Cyclic: Contains at least one cycle (a path that starts and ends at the same node).
- Acyclic: Contains no cycles. A DAG (Directed Acyclic Graph) is a crucial structure in scheduling and dependency resolution.
3. Graph Representations
How do we store a graph in code?
Adjacency Matrix
A 2D array where matrix[i][j] represents an edge from node i to node j.
- Pros: Fast lookup ($O(1)$) to check if an edge exists.
- Cons: Consumes $O(V^2)$ space. Bad for sparse graphs.
# 0 is not connected, 1 is connected
graph = [
[0, 1, 0], # Node 0 connects to 1
[1, 0, 1], # Node 1 connects to 0 and 2
[0, 1, 0] # Node 2 connects to 1
]Adjacency List
An array (or map) of lists. Each node stores a list of its neighbors.
- Pros: Saves space ($O(V + E)$). Good for sparse graphs.
- Cons: Slower lookup ($O(degree)$) to check if an edge exists.
graph = {
0: [1],
1: [0, 2],
2: [1]
}4. Graph Traversal
Breadth-First Search (BFS)
Explores neighbors layer by layer. Uses a Queue.
- Use Case: Finding the shortest path in an unweighted graph.
Depth-First Search (DFS)
Explores as far as possible along each branch before backtracking. Uses a Stack (or recursion).
- Use Case: Maze solving, cycle detection, topological sorting.
5. Common Algorithms
- Dijkstra's Algorithm: Finds the shortest path in a weighted graph (non-negative weights).
- *A (A-Star):** An extension of Dijkstra that uses heuristics to guide the search (used in pathfinding for games).
- Topological Sort: Linearly ordering vertices in a DAG such that for every directed edge $uv$, vertex $u$ comes before $v$.