📘 Introduction to Graph Theory

🧠 What is a Graph?

A graph is a non-linear data structure consisting of vertices (nodes) connected by edges (links). Graphs model relationships and connections between entities, making them fundamental for solving real-world problems like social networks, maps, dependencies, and more.

Think of a graph as a network where dots (vertices) are connected by lines (edges).

---

🎯 Why Learn Graph Theory?

Graphs are everywhere in computer science and the real world:

• 🌐 Social Networks — Friends, followers, connections
• 🗺️ Maps & Navigation — Cities connected by roads
• 🔗 Web Pages — Links between websites
• 📦 Dependencies — Package managers, build systems
• 🧬 Biology — Protein interactions, neural networks
• 💼 Recommendation Systems — Product/content suggestions

---

🛠️ Graph Basics

✅ Key Terminology

Term	Definition	Example
Vertex (Node)	A point in the graph	Cities in a map
Edge	Connection between two vertices	Road between cities
Degree	Number of edges connected to a vertex	Number of roads from a city
Path	Sequence of vertices connected by edges	Route from A to B
Cycle	Path that starts and ends at same vertex	Circular route
Connected Graph	Every vertex is reachable from any other	All cities are accessible

✅ Types of Graphs

1️⃣ Directed vs Undirected

Undirected Graph: Edges have no direction (bidirectional)

A ←→ B

Example: Facebook friendships (mutual)

Directed Graph (Digraph): Edges have direction

A → B

Example: Twitter follows (one-way)

2️⃣ Weighted vs Unweighted

Unweighted Graph: All edges are equal

A — B — C

Weighted Graph: Edges have values (costs, distances)

A —5— B —3— C

Example: Road network with distances

3️⃣ Cyclic vs Acyclic

Cyclic Graph: Contains at least one cycle

A → B → C → A

Acyclic Graph: No cycles

A → B → C

DAG (Directed Acyclic Graph): Directed graph with no cycles — used in task scheduling, dependency resolution

---

💾 Graph Representation

1️⃣ Adjacency Matrix

A 2D array where matrix[i][j] = 1 if there’s an edge from vertex i to vertex j.

# Graph: 0 — 1 — 2
#        |       |
#        3 ——————

graph = [
    [0, 1, 0, 1],  # 0 connects to 1, 3
    [1, 0, 1, 0],  # 1 connects to 0, 2
    [0, 1, 0, 1],  # 2 connects to 1, 3
    [1, 0, 1, 0]   # 3 connects to 0, 2
]

Pros: ✅ Fast edge lookup \(O(1)\)

Cons: ❌ Space inefficient \(O(V^2)\), slow to iterate neighbors

2️⃣ Adjacency List

A dictionary/array where each vertex stores a list of its neighbors.

# Same graph as above
graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

Pros: ✅ Space efficient \(O(V + E)\), fast neighbor iteration

Cons: ❌ Slower edge lookup \(O(degree)\)

👉 Most interview problems use adjacency lists!

3️⃣ Edge List

A list of all edges in the graph.

edges = [(0, 1), (1, 2), (2, 3), (0, 3)]

Use case: Useful for algorithms like Kruskal’s MST

---

🔍 Basic Graph Operations

Operation	Adjacency Matrix	Adjacency List
Add vertex	\(O(V^2)\)	\(O(1)\)
Add edge	\(O(1)\)	\(O(1)\)
Remove vertex	\(O(V^2)\)	\(O(V + E)\)
Remove edge	\(O(1)\)	\(O(V)\)
Check if edge exists	\(O(1)\)	\(O(V)\)
Find all neighbors	\(O(V)\)	\(O(1)\)

---

🚀 Core Graph Algorithms

🔹 1. Graph Traversal

Purpose: Visit all vertices in a graph

Breadth-First Search (BFS)

• Explores level by level (like ripples in water)
• Uses a queue
• Use cases: Shortest path in unweighted graphs, level-order traversal

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Time Complexity: \(O(V + E)\)

Depth-First Search (DFS)

• Explores as deep as possible before backtracking
• Uses a stack (or recursion)
• Use cases: Cycle detection, topological sort, connected components

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(vertex)
    print(vertex, end=' ')
    
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited

Time Complexity: \(O(V + E)\)

---

🔹 2. Shortest Path Algorithms

Dijkstra’s Algorithm

• Finds shortest path from source to all vertices
• Works with non-negative weights
• Uses priority queue (min-heap)

Time Complexity: \(O((V + E) \log V)\)

Bellman-Ford Algorithm

• Handles negative weights
• Detects negative cycles
• Slower than Dijkstra

Time Complexity: \(O(V \times E)\)

Floyd-Warshall Algorithm

• Finds shortest paths between all pairs of vertices
• Uses dynamic programming

Time Complexity: \(O(V^3)\)

---

🔹 3. Minimum Spanning Tree (MST)

Goal: Connect all vertices with minimum total edge weight

Kruskal’s Algorithm

• Sort edges by weight
• Add edges if they don’t create a cycle
• Uses Union-Find data structure

Time Complexity: \(O(E \log E)\)

Prim’s Algorithm

• Start from a vertex
• Greedily add minimum weight edge
• Uses priority queue

Time Complexity: \(O((V + E) \log V)\)

---

🔹 4. Topological Sort

Purpose: Linear ordering of vertices in a DAG

Use cases: Task scheduling, course prerequisites, build systems

def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(vertex)
    
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    
    return stack[::-1]  # Reverse to get correct order

Time Complexity: \(O(V + E)\)

---

🔹 5. Cycle Detection

In Undirected Graph: Use DFS with parent tracking

In Directed Graph: Use DFS with recursion stack (detect back edges)

---

🔹 6. Connected Components

Purpose: Find groups of connected vertices

def count_components(graph):
    visited = set()
    count = 0
    
    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
    
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
            count += 1
    
    return count

---

🧪 Example Problem: Number of Islands

Problem: Given a 2D grid of ‘1’s (land) and ‘0’s (water), count the number of islands.

def numIslands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0
    
    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            grid[r][c] == '0' or (r, c) in visited):
            return
        
        visited.add((r, c))
        # Explore 4 directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                dfs(r, c)
                count += 1
    
    return count

---

🎯 Common Graph Patterns

Pattern	When to Use	Example Problems
BFS	Shortest path, level-order	Word Ladder, Rotting Oranges
DFS	Explore all paths, backtracking	Number of Islands, Course Schedule
Union-Find	Connected components, cycles	Number of Provinces, Redundant Connection
Topological Sort	Dependency ordering	Course Schedule II, Alien Dictionary
Dijkstra	Weighted shortest path	Network Delay Time, Cheapest Flights

---

🕵️ How to Identify Graph Problems

Look for these keywords:

• “Connected”, “Network”, “Path”, “Route”
• “Dependencies”, “Prerequisites”, “Order”
• “Islands”, “Regions”, “Components”
• “Shortest”, “Minimum”, “Optimal”
• “Cycle”, “Loop”, “Circular”

---

💡 Problem-Solving Strategy

1. Identify the graph structure
   • What are the vertices? What are the edges?
   • Is it directed or undirected?
   • Is it weighted or unweighted?
2. Choose representation
   • Usually adjacency list for interviews
3. Select algorithm
   • Traversal? → BFS/DFS
   • Shortest path? → BFS (unweighted) or Dijkstra (weighted)
   • Ordering? → Topological sort
   • Components? → Union-Find or DFS
4. Handle edge cases
   • Empty graph, disconnected components, cycles

---

📊 Time Complexity Cheat Sheet

Algorithm	Time Complexity	Space Complexity
BFS	\(O(V + E)\)	\(O(V)\)
DFS	\(O(V + E)\)	\(O(V)\)
Dijkstra	\(O((V + E) \log V)\)	\(O(V)\)
Bellman-Ford	\(O(V \times E)\)	\(O(V)\)
Floyd-Warshall	\(O(V^3)\)	\(O(V^2)\)
Kruskal’s MST	\(O(E \log E)\)	\(O(V)\)
Prim’s MST	\(O((V + E) \log V)\)	\(O(V)\)
Topological Sort	\(O(V + E)\)	\(O(V)\)

---

✍️ Practice Assignments

1. Implement BFS and DFS for a given graph
2. Find if a path exists between two vertices
3. Detect a cycle in an undirected graph
4. Find the shortest path in an unweighted graph
5. Implement topological sort for a DAG

---

📝 Suggested Practice Problems

Easy

Medium

Hard

---

🔔 Next: Dive deeper into specific graph algorithms and solve real-world problems!