Introduction Graphs form the backbone of many systems we use daily—navigation apps, social networks, recommendation engines, and more. Understanding how to represent and traverse graphs is essential in computer science. This article focuses on elementary graph algorithms: how graphs are represented, and how to explore them using breadth-first search (BFS) and depth-first search (DFS).

---

Graph Representations Before running algorithms on a graph, we must decide how to represent it. The two most common representations are:

1. Adjacency List:
   • Space-efficient for sparse graphs.
   • Each vertex maintains a list of its neighbors.
   • Time to check edge existence: O(degree of vertex).
2. Adjacency Matrix:
   • Uses a 2D matrix (V x V) where V is the number of vertices.
   • Constant-time edge lookup: O(1).
   • Space-intensive for large or sparse graphs.

Example:

# Python adjacency list example
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

---

Breadth-First Search (BFS) BFS explores the graph in layers, visiting all neighbors at the current depth before going deeper.

Use Cases:

• Shortest path in unweighted graphs
• Finding connected components

Python Example:

from collections import deque

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

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            queue.extend([v for v in graph[vertex] if v not in visited])

Diagram: Imagine a graph: A — B — D, A — C — D Starting from A, BFS visits: A, B, C, D (in layer order)

---

Depth-First Search (DFS) DFS dives deep into each branch before backtracking.

Use Cases:

• Topological sorting
• Cycle detection
• Solving mazes

Python Example (Recursive):

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

Diagram: Using the same graph, DFS from A might visit: A, B, D, C

---

Real-World Case Studies

1. Facebook Friend Suggestions (BFS)
   • Facebook uses BFS to recommend friends: mutual friends within 2 degrees.
   • Efficiently implemented using adjacency lists due to the sparse nature of social graphs.
2. Google Maps (Shortest Path via BFS/DFS/Dijkstra)
   • For walking directions in grid-like cities, BFS is used due to uniform weights.
   • DFS is used internally for reachability and route existence checks.
3. Git Dependency Graph (DFS + Topological Sort)
   • Git uses DFS to identify commits that need merging and to visualize commit trees.

Real-World Case Studies

1. Facebook Friend Suggestions (BFS)
   • Facebook uses BFS to recommend friends: mutual friends within 2 degrees.
   • Efficiently implemented using adjacency lists due to the sparse nature of social graphs.
2. Google Maps (Shortest Path via BFS/DFS/Dijkstra)
   • For walking directions in grid-like cities, BFS is used due to uniform weights.
   • DFS is used internally for reachability and route existence checks.
3. Git Dependency Graph (DFS + Topological Sort)
   • Git uses DFS to identify commits that need merging and to visualize commit trees

---

Conclusion Elementary graph algorithms like BFS and DFS are not just academic concepts—they drive some of the most powerful systems today. With simple implementations and versatile applications, understanding these techniques is a foundational step for any programmer or systems engineer.

References

Even, S. (1979). Graph algorithms. https://openlibrary.org/books/OL4413422M/Graph_algorithms

Golumbic, M. C. (2004). Algorithmic graph theory and perfect graphs. In Annals of discrete mathematics. https://doi.org/10.1016/s0167-5060(04)x8001-8