Graphs

What is a graph?

A graph is a set of nodes connected by edges. Unlike a tree (which has one root and no cycles), a graph can have any connections, including loops. Graphs model relationships — and they’re everywhere in mobile apps.

Graphs in mobile apps

• Social networks — users are nodes, friendships are edges (“friends of friends”).
• Maps & navigation — places are nodes, roads are edges with distances (weights); routing finds the shortest path.
• App navigation graph — screens connected by possible transitions (literally called a “nav graph”).
• Dependencies — tasks/modules that depend on each other.

Representing a graph

The common, memory-friendly representation is an adjacency list: a map from each node to its neighbours.

val graph = mapOf(
    "A" to listOf("B", "C"),
    "B" to listOf("A", "D"),
    "C" to listOf("D"),
    "D" to listOf("B", "C")
)

Traversal: BFS and DFS

The two ways to explore a graph mirror tree traversal — with one crucial addition: you must track visited nodes, or cycles cause infinite loops.

// BFS — finds the shortest path in an unweighted graph (fewest hops)
fun bfs(start: String): Set<String> {
    val visited = mutableSetOf(start)
    val queue = ArrayDeque(listOf(start))
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        for (next in graph[node].orEmpty()) {
            if (visited.add(next)) queue.add(next)   // add() = not visited before
        }
    }
    return visited
}

• BFS (queue) — explores level by level; great for “shortest number of steps” (e.g. degrees of connection).
• DFS (stack/recursion) — goes deep; great for “is there any path” or exploring all reachable nodes.

Weighted graphs & shortest path

When edges have costs (distance, time), finding the cheapest route uses algorithms like Dijkstra’s. You won’t implement Google Maps, but understanding this explains how routing and “nearest” features work, and you may use a graph for smaller in-app routing or recommendations.

Mobile considerations

• Graph algorithms can be expensive — run them off the main thread.
• Always track visited nodes to avoid infinite loops on cyclic graphs.
• Adjacency lists are far more memory-efficient than adjacency matrices for sparse graphs (most real ones).

Common mistakes

• Forgetting the visited set → infinite loop on cycles.
• Using BFS/DFS on the main thread for a large graph (jank/ANR).
• Choosing a matrix representation for a sparse graph (wastes memory).

Summary: Graphs model connections — social links, maps, nav graphs. Store them as adjacency lists, traverse with BFS (queue, shortest hops) or DFS (stack/recursion, deep exploration), always track visited nodes to handle cycles, and run heavy graph work off the main thread.