Overview

A graph is a collection of nodes, called vertices, and edges connecting pairs of vertices. Graphs are used to represent relationships between objects.

Types of Graphs

  1. Undirected Graph: Edges have no direction.
  2. Directed Graph (Digraph): Edges have a direction.
  3. Weighted Graph: Edges have weights or costs associated with them.
  4. Unweighted Graph: Edges do not have weights.
  5. Cyclic Graph: Contains at least one cycle.
  6. Acyclic Graph: Does not contain any cycles.
  7. Connected Graph: All vertices are connected by some path.
  8. Disconnected Graph: At least one vertex is not reachable from others.

Graph Representations

1. Adjacency Matrix

A 2D array where matrix[i][j] indicates if there is an edge between vertex i and vertex j.

  • Space Complexity: O(V²)
  • Example: 
    # Adjacency Matrix Representation
graph = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
]

2. Adjacency List

A list of lists or a dictionary where each key represents a vertex and its value is a list of adjacent vertices.

  • Space Complexity: O(V + E)
  • Example: 
    # Adjacency List Representation
graph = {
    0: [1],
    1: [0, 2],
    2: [1]
}

Graph Traversal Techniques

1. Breadth-First Search (BFS)

  • Explores all neighbors of a node before moving to the next level.
  • Data Structure: Queue
  • Time Complexity: O(V + E)
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            result.append(node)
            queue.extend(graph[node])

    return result

# Example Usage
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}
print(bfs(graph, 0))  # Output: [0, 1, 2, 3]

2. Depth-First Search (DFS)

  • Explores as far as possible along a branch before backtracking.
  • Data Structure: Stack (or recursion)
  • Time Complexity: O(V + E)
# Recursive DFS
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    result = [node]

    for neighbor in graph[node]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))

    return result

# Example Usage
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}
print(dfs(graph, 0))  # Output: [0, 1, 3, 2]

Graph Algorithms

1. Dijkstra’s Algorithm

Finds the shortest path from a source vertex to all other vertices in a weighted graph.

  • Data Structure: Priority Queue
  • Time Complexity: O((V + E) * log(V))
import heapq

def dijkstra(graph, start):
    pq = [(0, start)]  # (distance, node)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# Example Usage
graph = {
    0: [(1, 1), (2, 4)],
    1: [(2, 2), (3, 6)],
    2: [(3, 3)],
    3: []
}
print(dijkstra(graph, 0))  # Output: {0: 0, 1: 1, 2: 3, 3: 6}

2. Topological Sort

Sorts vertices of a directed acyclic graph (DAG) in linear order.

  • Data Structure: Stack
  • Time Complexity: O(V + E)
# Topological Sort Using DFS

def topological_sort(graph):
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)

    visited = set()
    stack = []

    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]

# Example Usage
graph = {
    5: [2, 0],
    4: [0, 1],
    3: [1],
    2: [3],
    1: [],
    0: []
}
print(topological_sort(graph))  # Output: [5, 4, 2, 3, 1, 0]

3. Detect Cycle in a Graph

Check if a graph contains any cycles.

  • Directed Graph: Use DFS and track recursion stack.
  • Undirected Graph: Use DFS and track visited nodes and parent node.
# Detect Cycle in Directed Graph

def has_cycle(graph):
    def dfs(node):
        visited.add(node)
        recursion_stack.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in recursion_stack:
                return True

        recursion_stack.remove(node)
        return False

    visited = set()
    recursion_stack = set()

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True

    return False

# Example Usage
graph = {
    0: [1],
    1: [2],
    2: [0]
}
print(has_cycle(graph))  # Output: True

Summary

Graphs are a fundamental data structure used to solve problems in navigation, networking, social networks, and more. Mastering traversal techniques and algorithms like Dijkstra’s, Topological Sort, and cycle detection is crucial for solving graph-related problems efficiently.