Graph Traversal Algorithms in Swift!

GraphTraversals.swift

/// Playground Demonstrating Common Graph Traversal Algorithms

struct GraphNode: Hashable {
    let label: String
    //let neighbors: Set<GraphNode>
    
    init(label: String) {
        self.label = label
        //self.neighbors = Set<GraphNode>()
    }
}

let nodeA = GraphNode(label: "A")
let nodeB = GraphNode(label: "B")
let nodeC = GraphNode(label: "C")
let nodeD = GraphNode(label: "D")
let nodeE = GraphNode(label: "E")
let nodeF = GraphNode(label: "F")
let nodeG = GraphNode(label: "G")

/// Here, we make a graph dictionary where we set each node's
/// adjacent neighbors. You could uncomment the the neighbors property
/// in the GraphNode struct however and individually set the neighbors that way.
let graph: [String : [GraphNode]] = {
    var graph = [String : [GraphNode]]()
    /// change the values to make new graphs
    graph[nodeA.label] = [nodeB, nodeC, nodeG]
    graph[nodeB.label] = [nodeD, nodeE]
    graph[nodeC.label] = [nodeD]
    graph[nodeD.label] = [nodeE, nodeF]
    graph[nodeE.label] = []
    graph[nodeF.label] = [nodeG]
    graph[nodeG.label] = [nodeC]
    return graph
}()


func iterativeDepthFirstTraversal(graph: [String : [GraphNode]], node: GraphNode) -> [GraphNode] {
    var visitedNodes = [GraphNode]()
    var stack = [node]
    
    while stack.count > 0 {
        let vertex = stack.popLast()!
        if !visitedNodes.contains(vertex) {
            visitedNodes.append(vertex)
            for neighbor in graph[vertex.label]! {
                stack.append(neighbor)
            }
        }
        
    }

    return visitedNodes
}

print("Visited Nodes")
let visitedNodesList = iterativeDepthFirstTraversal(graph: graph, node: nodeA)
visitedNodesList.forEach { (visitedNode) in
    print(visitedNode)
}

print("\n")

func recursiveDepthFirstTraversal(graph: [String : [GraphNode]], node: GraphNode, visited: inout [GraphNode]) {
    if !visited.contains(node) {
        visited.append(node)
        let neighbors = graph[node.label]
        neighbors?.forEach({ (neighbor) in
            recursiveDepthFirstTraversal(graph: graph, node: neighbor, visited: &visited)
        })
    }
}

let startingNode = nodeA
var visitedStack = [GraphNode]()
recursiveDepthFirstTraversal(graph: graph, node: startingNode, visited: &visitedStack)
print("Recursively Visited Nodes")
visitedStack.forEach { (visitedNode) in
    print(visitedNode)
}
print("\n")

func iterativeBreadthFirstTraversal(graph: [String: [GraphNode]], node: GraphNode) -> Set<GraphNode> {
    var visitedSet = Set<GraphNode>()
    var queue = [GraphNode]()
    queue.append(node)
    var front = 0
    var size = 1
    while size > 0 {
        size -= 1
        let poppedNode = queue[front]
        if !visitedSet.contains(poppedNode) {
            visitedSet.insert(poppedNode)
            let neighbors = graph[poppedNode.label]
            neighbors?.forEach({ (neighbor) in
                if !visitedSet.contains(neighbor) {
                    size += 1
                    queue.append(neighbor)
                }
            })
            
        }
        front += 1

    }
    return visitedSet
}

let breadthVisited = iterativeBreadthFirstTraversal(graph: graph, node: nodeA)
print("Iterative Breadth First Visited")
breadthVisited.forEach { (node) in
    print(node)
}