Graphs, Trees & Traversal (BFS/DFS)

Overview

A graph is a set of nodes connected by edges — the natural model for anything relational: social networks, knowledge graphs, molecules, web links, and recommendation systems (users and items as nodes). Trees are a special acyclic case used for hierarchies, parsing, and decision trees. Two traversals are fundamental: breadth-first search (BFS) explores level by level and finds shortest paths in unweighted graphs, while depth-first search (DFS) plunges down one path before backtracking and is used for reachability, cycle detection, and topological ordering of DAGs (which model task/computation dependencies). Directed acyclic graphs are especially relevant to AI: the computation graph a framework builds for autograd is a DAG, and pipelines/dependencies are DAGs too. Graph Neural Networks generalise deep learning to this structure, letting nodes aggregate information from their neighbours — powering fraud detection, molecule property prediction, and modern recommenders.

Represent a graph and traverse it (BFS)

from collections import deque

graph = {
    "A": ["B", "C"], "B": ["A", "D"],
    "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"],
}

def bfs(start):
    seen, order, q = {start}, [], deque([start])
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb); q.append(nb)
    return order

print(bfs("A"))   # ['A','B','C','D','E'] level by level

DFS and DAGs: dependency ordering

deps = {                      # a DAG of task dependencies
    "data": [], "clean": ["data"],
    "train": ["clean"], "eval": ["train"], "deploy": ["eval"],
}

def toposort(g):
    seen, order = set(), []
    def dfs(n):
        if n in seen: return
        seen.add(n)
        for m in g[n]: dfs(m)
        order.append(n)          # add after visiting dependencies
    for n in g: dfs(n)
    return order

print(toposort(deps))   # ['data','clean','train','eval','deploy']

Key Points to Remember

• 1Graphs = nodes + edges; the model for relational data (social, knowledge, recommenders)
• 2BFS explores level by level (shortest paths); DFS goes deep (reachability, cycles)
• 3DAGs model dependencies — including the autograd computation graph
• 4Graph Neural Networks let nodes aggregate neighbour info — fraud, molecules, recommendations