Elementary Graph Algorithms Explained

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:

Adjacency List:
- Space-efficient for sparse graphs.
- Each vertex maintains a list of its neighbors.
- Time to check edge existence: O(degree of vertex).
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

Minimum Spanning Trees (MSTs) A Minimum Spanning Tree connects all nodes in a graph with the smallest possible total edge weight. Two key greedy algorithms for computing MSTs are:

Kruskal’s Algorithm:
- Sorts all edges by weight.
- Adds edges one by one, skipping any that create a cycle (using Union-Find).

Python Implementation:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX
            return True
        return False

def kruskal(n, edges):
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    edges.sort(key=lambda x: x[2])
    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
    return mst, total_weight

Prim’s Algorithm:
- Grows the MST starting from an arbitrary vertex.
- Uses a priority queue to pick the next closest edge.

Python Implementation:

import heapq

def prim(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_weight = 0

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)
        if vertex not in visited:
            visited.add(vertex)
            total_weight += weight
            for neighbor, w in graph[vertex]:
                if neighbor not in visited:
                    heapq.heappush(min_heap, (w, neighbor))
    return total_weight

Example Graph:

# For Prim's algorithm
graph = {
    0: [(1, 4), (2, 1)],
    1: [(0, 4), (2, 3), (3, 2)],
    2: [(0, 1), (1, 3), (3, 4)],
    3: [(1, 2), (2, 4)]
}

Use Cases:

Network design (laying cables or roads at minimal cost)
Circuit design (wiring layout with minimal material)

Real-World Case Studies

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.
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.
Git Dependency Graph (DFS + Topological Sort)
- Git uses DFS to identify commits that need merging and to visualize commit trees.
Telecommunication Network Design (MSTs)
- Companies use MSTs to minimize the cost of connecting communication towers across regions.
- Kruskal’s algorithm is preferred when edges are sparse and already known.

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

Syslo, M. M. (1973). Algorithm 459: the elementary circuits of a graph. Communications of the ACM, 16(10), 632–633. https://doi.org/10.1145/362375.362406

Brassard, G., & Bratley, P. (1996). Fundamentals of algorithmics. In Prentice-Hall, Inc eBooks (p. 524). https://ci.nii.ac.jp/ncid/BA26605678

Elementary Graph Algorithms Explained: Concepts, Code, and Real-World Use Cases

References

scrolls