Graphs

Overview

A graph is a non-linear data structure that represents relationships between entities. It consists of nodes (also called vertices) connected by edges. Graphs are ubiquitous in computer science and are used in applications such as social networks, navigation systems, and dependency resolution.

Key Terminology

• Vertex (Node): A fundamental unit of the graph.

• Edge: A connection between two vertices.

• Directed Graph: Edges have direction (e.g., from A to B).

• Undirected Graph: Edges have no direction.

• Weighted Graph: Edges have associated weights (e.g., distances, costs).

• Adjacency List: Stores each vertex and a list of its adjacent vertices.

• Adjacency Matrix: A 2D matrix indicating edges between vertices.

Graph Representations in Swift

1. Using Adjacency List

struct Edge<T: Hashable> {
    let destination: T
    let weight: Double?
}

class Graph<T: Hashable> {
    private(set) var adjacencyList: [T: [Edge<T>]] = [:]

    func addVertex(_ vertex: T) {
        adjacencyList[vertex] = []
    }

    func addEdge(from source: T, to destination: T, weight: Double? = nil, directed: Bool = false) {
        adjacencyList[source, default: []].append(Edge(destination: destination, weight: weight))
        if !directed {
            adjacencyList[destination, default: []].append(Edge(destination: source, weight: weight))
        }
    }

    func neighbors(of vertex: T) -> [Edge<T>] {
        adjacencyList[vertex] ?? []
    }
}

Graph Traversal Algorithms

1. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking.

func dfs<T: Hashable>(graph: Graph<T>, start: T, visited: inout Set<T>) {
    guard !visited.contains(start) else { return }

    visited.insert(start)
    print(start)

    for edge in graph.neighbors(of: start) {
        dfs(graph: graph, start: edge.destination, visited: &visited)
    }
}

Usage:

var visited: Set<String> = []
dfs(graph: myGraph, start: "A", visited: &visited)

2. Breadth-First Search (BFS)

BFS explores neighbors level by level using a queue.

func bfs<T: Hashable>(graph: Graph<T>, start: T) {
    var visited: Set<T> = [start]
    var queue: [T] = [start]

    while !queue.isEmpty {
        let vertex = queue.removeFirst()
        print(vertex)

        for edge in graph.neighbors(of: vertex) {
            if !visited.contains(edge.destination) {
                visited.insert(edge.destination)
                queue.append(edge.destination)
            }
        }
    }
}

Topological Sort (for DAGs)

Used for scheduling tasks where some tasks must be completed before others.

func topologicalSort<T: Hashable>(graph: Graph<T>) -> [T]? {
    var visited: Set<T> = []
    var stack: [T] = []
    var visiting: Set<T> = []

    func dfs(_ vertex: T) -> Bool {
        if visiting.contains(vertex) { return false }
        if visited.contains(vertex) { return true }

        visiting.insert(vertex)
        for edge in graph.neighbors(of: vertex) {
            if !dfs(edge.destination) { return false }
        }

        visiting.remove(vertex)
        visited.insert(vertex)
        stack.append(vertex)
        return true
    }

    for vertex in graph.adjacencyList.keys {
        if !visited.contains(vertex) {
            if !dfs(vertex) { return nil } // cycle detected
        }
    }

    return stack.reversed()
}

Dijkstra’s Algorithm (Shortest Path)

Efficiently finds the shortest path from a source to all other vertices in a weighted graph.

func dijkstra<T: Hashable>(graph: Graph<T>, source: T) -> [T: Double] {
    var distances: [T: Double] = [source: 0]
    var priorityQueue: [(vertex: T, cost: Double)] = [(source, 0)]

    while !priorityQueue.isEmpty {
        let (current, cost) = priorityQueue.removeFirst()

        guard cost <= (distances[current] ?? Double.infinity) else { continue }

        for edge in graph.neighbors(of: current) {
            guard let weight = edge.weight else { continue }
            let newDistance = cost + weight
            if newDistance < (distances[edge.destination] ?? Double.infinity) {
                distances[edge.destination] = newDistance
                priorityQueue.append((edge.destination, newDistance))
            }
        }

        priorityQueue.sort { $0.cost < $1.cost } // acts like a min-heap
    }

    return distances
}

Use Case Example

let graph = Graph<String>()
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addEdge(from: "A", to: "B", weight: 2)
graph.addEdge(from: "B", to: "C", weight: 3)
graph.addEdge(from: "A", to: "C", weight: 5)

let shortestPaths = dijkstra(graph: graph, source: "A")
print(shortestPaths) // ["A": 0.0, "B": 2.0, "C": 5.0]

Complexity Overview

Summary

Graphs are powerful tools for modeling real-world systems and solving complex problems. By understanding how to represent and traverse graphs in Swift, you unlock the ability to implement routing, scheduling, and relationship-driven algorithms with elegance and efficiency.