Graphs

Graph Representation

Graphs can be represented in various ways, but two of the most common representations are adjacency matrix and adjacency list.

Adjacency Matrix

An adjacency matrix is a 2D array where rows and columns represent nodes, and the presence or absence of an edge between nodes is represented by values (e.g., 1 or 0 for unweighted graphs, or the weight for weighted graphs).

• Space Complexity: O(V²), where V is the number of vertices.
• Pros: Fast lookups to check if an edge exists between two nodes.
• Cons: Takes up more space, especially in sparse graphs.

Example for Adjacency Matrix

from typing import List

def create_adjacency_matrix(n: int, edges: List[tuple[int, int, int]]) -> List[List[int]]:
    """
    Creates an adjacency matrix for a graph with n nodes.
    - n: Number of nodes
    - edges: List of edges, where each edge is represented as (u, v, weight)
    """
    matrix = [[0] * n for _ in range(n)]  # Initialize a 2D matrix with zeros
    for u, v, weight in edges:
        matrix[u][v] = weight  # Add the edge
        # For undirected graphs, add the opposite edge
        matrix[v][u] = weight
    return matrix

Adjacency List

An adjacency list uses a dictionary or list of lists to represent the graph. Each node has a list of neighbors, making it ideal for sparse graphs.

• Space Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
• Pros: Efficient in space for sparse graphs and easier to traverse.
• Cons: Checking for the existence of an edge between two nodes is slower.

Code Example for Adjacency List

from typing import Dict, List
def create_adjacency_list(n: int, edges: List[tuple[int, int, int]]) -> Dict[int, List[tuple[int, int]]]:
    """
    Creates an adjacency list for a graph with n nodes.
    - n: Number of nodes
    - edges: List of edges, where each edge is represented as (u, v, weight)
    """
    adj_list = {i: [] for i in range(n)}  # Initialize an adjacency list with empty lists for each node
    
    for u, v, weight in edges:
        adj_list[u].append((v, weight))  # Add the edge
        # For undirected graphs, add the opposite edge
        adj_list[v].append((u, weight))
    return adj_list

Graph Traversal: Depth-First Search (DFS) and Breadth-First Search (BFS)

Traversal algorithms like DFS and BFS are crucial for exploring graphs and are often used to solve various problems, such as finding connected components or checking for cycles.

Depth-First Search (DFS)

DFS explores as far down a branch as possible before backtracking, making it a stack-based approach. It can be implemented recursively or iteratively.

DFS Implementation (Recursive)

from typing import List

def dfs_recursive(node: int, visited: List[bool], adj_list: Dict[int, List[int]]) -> None:
    """
    Depth-First Search recursive function.
    - node: The current node to visit
    - visited: List indicating if a node has been visited
    - adj_list: The graph represented as an adjacency list
    """
    visited[node] = True  # Mark the current node as visited
    print(f"Visited {node}")
    for neighbor, _ in adj_list[node]:
        if not visited[neighbor]:
            dfs_recursive(neighbor, visited, adj_list)

Tip: Use a boolean visited array or set to avoid revisiting nodes, especially in undirected graphs.

Breadth-First Search (BFS)

BFS explores nodes level by level, making it a queue-based approach. It’s ideal for finding the shortest path in an unweighted graph.

BFS Implementation (Iterative)

from collections import deque
def bfs(start: int, adj_list: Dict[int, List[int]]) -> None:
    """
    Breadth-First Search using a queue.
    - start: The starting node for BFS
    - adj_list: The graph represented as an adjacency list
    """
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        if node not in visited:
            visited.add(node)
            print(f"Visited {node}")
            for neighbor, _ in adj_list[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

Tip: BFS is ideal for unweighted shortest-path problems. Always consider it when the problem involves finding the shortest paths in unweighted graphs.

Directed vs Undirected Graphs

• Directed Graphs: In a directed graph, edges have a direction, meaning an edge (u, v) goes from u to v but not vice versa. Directed graphs are useful for modeling dependencies or one-way relationships.
• Undirected Graphs: In an undirected graph, edges have no direction, meaning an edge (u, v) implies a two-way connection between u and v. Undirected graphs are ideal for modeling bi-directional relationships.

Tip: If the graph type is not explicitly stated, clarify whether it’s directed or undirected. This will affect both traversal and cycle-detection algorithms.

Weighted vs Unweighted Graphs

• Weighted Graphs: In a weighted graph, each edge has a numerical weight or cost. Weighted graphs are often used in pathfinding algorithms, where finding the shortest or minimum-cost path is necessary (e.g., Dijkstra’s algorithm).
• Unweighted Graphs: In an unweighted graph, edges have no weights, and each edge represents a uniform “cost.” BFS can find the shortest path in unweighted graphs since each edge has an equal cost.

Tip: In interviews, always clarify whether weights are involved when a problem involves paths or distances. If weights are involved, it might lead to algorithms like Dijkstra’s or Bellman-Ford.