Graphs

Master non-linear data structures with vertices and edges

🕸️ What are Graphs?

Graphs are non-linear data structures consisting of vertices (nodes) connected by edges. They represent relationships between objects and are used in social networks, maps, computer networks, and many other applications. 


# Basic graph representation
class Graph:
    def __init__(self):
        self.vertices = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []
    
    def add_edge(self, v1, v2):
        self.vertices[v1].append(v2)
        self.vertices[v2].append(v1)  # Undirected
V + E
Space
O(V + E)
Traversal
Networks
Applications

Graph Types

↔️

Undirected

Edges have no direction

Social networks Friendships
➡️

Directed

Edges have specific direction

Web pages Dependencies
⚖️

Weighted

Edges have associated costs

Road networks Shortest paths
🔄

Cyclic

Contains cycles or loops

Circuit detection Deadlock detection

Lesson 1: Graph Representation

Two main ways to represent graphs:

Adjacency List 

class Graph:
    def __init__(self):
        self.graph = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, v1, v2):
        self.graph[v1].append(v2)
        self.graph[v2].append(v1)  # For undirected graph
    
    def display(self):
        for vertex in self.graph:
            print(f"{vertex}: {self.graph[vertex]}")

# Example usage
g = Graph()
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.display()
# Output:
# A: ['B']
# B: ['A', 'C']  
# C: ['B']
Adjacency Matrix 

class GraphMatrix:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]
        self.vertices = {}
        self.vertex_count = 0
    
    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = self.vertex_count
            self.vertex_count += 1
    
    def add_edge(self, v1, v2):
        i, j = self.vertices[v1], self.vertices[v2]
        self.matrix[i][j] = 1
        self.matrix[j][i] = 1  # Undirected
    
    def display(self):
        for row in self.matrix:
            print(row)

# Example usage
gm = GraphMatrix(3)
gm.add_vertex('A')
gm.add_vertex('B')
gm.add_vertex('C')
gm.add_edge('A', 'B')
gm.add_edge('B', 'C')
gm.display()
# Output:
# [0, 1, 0]
# [1, 0, 1]
# [0, 1, 0]

Lesson 2: Graph Traversal

Two main traversal algorithms:

Depth-First Search (DFS) 

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

def dfs_iterative(self, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            
            # Add neighbors to stack
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

# Add to Graph class
Graph.dfs = dfs
Graph.dfs_iterative = dfs_iterative

# Test DFS
g = Graph()
for v in ['A', 'B', 'C', 'D']:
    g.add_vertex(v)
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')

print("DFS traversal:")
g.dfs('A')  # Output: A B D C
Breadth-First Search (BFS) 

from collections import deque

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

def bfs_shortest_path(self, start, end):
    """Find shortest path between two vertices"""
    if start == end:
        return [start]
    
    visited = set()
    queue = deque([(start, [start])])
    visited.add(start)
    
    while queue:
        vertex, path = queue.popleft()
        
        for neighbor in self.graph[vertex]:
            if neighbor == end:
                return path + [neighbor]
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path found

# Add to Graph class
Graph.bfs = bfs
Graph.bfs_shortest_path = bfs_shortest_path

print("\nBFS traversal:")
g.bfs('A')  # Output: A B C D

print(f"\nShortest path A to D: {g.bfs_shortest_path('A', 'D')}")

Lesson 3: Shortest Path Algorithms

Find the shortest path in weighted graphs:

Dijkstra's Algorithm 

import heapq

class WeightedGraph:
    def __init__(self):
        self.graph = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, v1, v2, weight):
        self.graph[v1].append((v2, weight))
        self.graph[v2].append((v1, weight))  # Undirected
    
    def dijkstra(self, start):
        distances = {vertex: float('infinity') for vertex in self.graph}
        distances[start] = 0
        pq = [(0, start)]
        visited = set()
        
        while pq:
            current_distance, current_vertex = heapq.heappop(pq)
            
            if current_vertex in visited:
                continue
            
            visited.add(current_vertex)
            
            for neighbor, weight in self.graph[current_vertex]:
                distance = current_distance + weight
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(pq, (distance, neighbor))
        
        return distances

# Example usage
wg = WeightedGraph()
for v in ['A', 'B', 'C', 'D']:
    wg.add_vertex(v)

wg.add_edge('A', 'B', 4)
wg.add_edge('A', 'C', 2)
wg.add_edge('B', 'C', 1)
wg.add_edge('B', 'D', 5)
wg.add_edge('C', 'D', 8)

distances = wg.dijkstra('A')
print("Shortest distances from A:", distances)
# Output: {'A': 0, 'B': 3, 'C': 2, 'D': 8}

Lesson 4: Cycle Detection

Detect cycles in graphs:

Cycle Detection in Undirected Graph 

def has_cycle_undirected(self):
    """Detect cycle in undirected graph using DFS"""
    visited = set()
    
    def dfs(vertex, parent):
        visited.add(vertex)
        
        for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif neighbor != parent:
                return True  # Back edge found
        
        return False
    
    for vertex in self.graph:
        if vertex not in visited:
            if dfs(vertex, None):
                return True
    
    return False

def has_cycle_directed(self):
    """Detect cycle in directed graph using DFS"""
    WHITE, GRAY, BLACK = 0, 1, 2
    colors = {vertex: WHITE for vertex in self.graph}
    
    def dfs(vertex):
        colors[vertex] = GRAY
        
        for neighbor in self.graph[vertex]:
            if colors[neighbor] == GRAY:
                return True  # Back edge found
            elif colors[neighbor] == WHITE and dfs(neighbor):
                return True
        
        colors[vertex] = BLACK
        return False
    
    for vertex in self.graph:
        if colors[vertex] == WHITE:
            if dfs(vertex):
                return True
    
    return False

# Add to Graph class
Graph.has_cycle_undirected = has_cycle_undirected
Graph.has_cycle_directed = has_cycle_directed

# Test cycle detection
cycle_graph = Graph()
for v in ['A', 'B', 'C']:
    cycle_graph.add_vertex(v)

cycle_graph.add_edge('A', 'B')
cycle_graph.add_edge('B', 'C')
cycle_graph.add_edge('C', 'A')  # Creates cycle

print(f"Has cycle: {cycle_graph.has_cycle_undirected()}")  # True

Real-World Applications

Social Networks

  • Friend connections
  • Influence propagation
  • Community detection
  • Recommendation systems

Navigation Systems

  • GPS routing
  • Traffic optimization
  • Shortest path finding
  • Route planning

Computer Networks

  • Internet topology
  • Network routing
  • Load balancing
  • Fault tolerance

Dependency Management

  • Package managers
  • Build systems
  • Task scheduling
  • Topological sorting

🧠 Test Your Knowledge

What is the time complexity of BFS traversal?

Which algorithm finds shortest paths in weighted graphs?