Imagine you're looking for a specific file on your hard drive. You start at the root directory, open a folder called "Projects," then "SwiftCourse," then "Lessons," and finally find "Lesson222.md." You've just performed a tree traversal. Now, imagine you're using a map app to find the fastest way from your house to a coffee shop. You might check a few different street combinations, some of which loop back on themselves or intersect at multiple points. That's a graph problem.

When we map these to code, the "folders" or "intersections" become Nodes (or Vertices), and the "contains" relationship or the "road" connecting them becomes the Edge. The big difference is that a tree is just a restricted version of a graph—it's a graph where there's only one path between any two nodes and no cycles. If you can go in a circle, you're officially dealing with a graph.

Why Classes Over Structs for Nodes

In previous lessons, I've pushed you toward structs for almost everything. But when we build trees and graphs, we usually switch to class. Why? Because nodes need to refer to other nodes. If you try to put a struct inside itself, Swift will scream at you because the size of the value would be infinite. While you could use an indirect enum, classes are the industry standard here because they provide reference semantics. When you update a node's value in a graph, you want every other node pointing to it to see that change immediately.

class Node<T> {
    var value: T
    var children: [Node<T>] = []
    
    init(_ value: T) {
        self.value = value
    }
}

Going Deep with Depth-First Search

Depth-First Search (DFS) is like that one person who enters a maze and refuses to turn back until they hit a dead end. In Swift, the cleanest way to implement this is through recursion. You visit a node, then immediately dive into its first child, then that child's first child, and so on.

I often use DFS when I need to explore every single possibility or when I'm searching for something that is likely buried deep in the hierarchy. The call stack handles the "remembering" of where to go back to once you hit a leaf node.

func depthFirstSearch(node: Node<String>, target: String) -> Bool {
    if node.value == target { return true }
    
    for child in node.children {
        if depthFirstSearch(node: child, target: target) {
            return true
        }
    }
    return false
}

Exploring the Neighborhood with Breadth-First Search

BFS is different. It's like a ripple in a pond. You check the root, then all of its immediate children, then all of their children. If you're looking for the shortest path in an unweighted graph, BFS is your only real option. Because it explores layer by layer, the first time you find your target, you can be certain you found the quickest way there.

Since we can't use recursion to go "wide," we use a Queue. I'll be honest: Swift doesn't have a built-in Queue type in the standard library, so we usually just use an Array and removeFirst(), even though that's technically O(n). For a production app, you'd want a proper doubly-linked list queue, but for most algorithm problems, an array suffices.

func breadthFirstSearch(root: Node<String>, target: String) -> Bool {
    var queue: [Node<String&gt>] = [root]
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        if current.value == target { return true }
        queue.append(contentsOf: current.children)
    }
    return false
}

Handling the "Infinite Loop" in Graphs

Here is where graphs get dangerous. In a tree, you can't get lost because there are no loops. In a graph, you can have a node that points back to its own ancestor. If you run the DFS or BFS code above on a graph with a cycle, your app will crash with a stack overflow or run forever.

The fix is simple but mandatory: keep a Set of visited nodes. Before you process a node, check if it's in the set. If it is, skip it. If not, add it and keep moving. Since we are using classes, we can make our Node conform to Hashable by using the object's identity (ObjectIdentifier) to ensure we're tracking the specific instance, not just a node with the same value.

📋 Practical Task

Build a Package Dependency Resolver

In software engineering, a "Dependency Graph" represents which libraries your project needs. Some libraries depend on other libraries, and sometimes you have circular dependencies (which is usually a bad thing!).

Your Task: Create a PackageNode class and a DependencyResolver class. The resolver should have a method called detectCircularDependency(root: PackageNode) -> Bool.

Requirements:

• PackageNode should have a name: String and a list of dependencies: [PackageNode].
• The resolver must use a Depth-First Search (DFS) approach.
• You must track the "current path" of the recursion. If you encounter a node that is already in the current recursion stack, you've found a cycle.
• Test your code with two scenarios:
  1. A healthy chain: App $\rightarrow$ NetworkLib $\rightarrow$ LoggingLib (Should return false).
  2. A circular chain: App $\rightarrow$ NetworkLib $\rightarrow$ LoggingLib $\rightarrow$ App (Should return true).