Graph Search Algorithms in 100 Seconds - And Beyond with Swiftt

nodes.swift

#!/usr/bin/env swift

// This is a Swift implementation of Fireship's "Graph Search Algorithms in 100 seconds - And beyond with JS" video
// You can find it here: https://www.youtube.com/watch?v=cWNEl4HE2OE

let airports = "PHX BKK OKC JFK LAX MEX HEL LAP LIM".split(separator: " ")

let routes = [
	["PHX", "LAX"],
	["PHX", "JFK"],
	["JFK", "OKC"],
	["JFK", "HEL"],
	["JFK", "LOS"],
	["MEX", "LAX"],
	["MEX", "BKK"],
	["MEX", "LIM"],
	["MEX", "EZE"],
	["LIM", "BKK"],
]

var adjList: [String: [String]] = [:]

// Extend [String: [String]]
extension Dictionary where Key == String, Value == [String] {
	/// Add an undirected edge
	mutating func addEdge(origin: String, dest: String) {
		if self[origin] != nil { self[origin]!.append(dest) } else { self[origin] = [dest] }
		if self[dest]   != nil { self[dest]!.append(origin) } else { self[dest] = [origin] }
	}
}

// Create the graph
airports.forEach { ap in 
	adjList[String(ap)] = []
}
routes.forEach { route in 
	adjList.addEdge(origin: route[0], dest: route[1])
}

print(adjList)

print("==================")

// BFS (Breadth First Search) //

extension Dictionary where Key == String, Value == [String] {
	/// - `start`: starting node
	func bfs(start: String) {

		var visited: Set<String> = []

		var queue: [String] = [start]

		while queue.count > 0 {
			let airport = queue.removeFirst()
			// Get airport's destinations (children)
			let destinations = self[airport]! // self = adjList

			for destination in destinations {
				if destination == "BKK" {
					print("BFS found Bangkok")
				}

				if !visited.contains(destination) {
					visited.insert(destination)
					queue.append(destination)
					print(destination)
				}
			}
		}
	}
}

adjList.bfs(start: "PHX")

print("==================")

// DFS (Depth First Search) //

extension Dictionary where Key == String, Value == [String] {
	/// - `start`: starting node
	func dfs(start: String, visited _visited: Set<String> = []) {
		var visited = _visited

		print(start)

		visited.insert(start)

		let destinations = self[start]!

		for destination in destinations {
			if destination == "BKK" {
				print("DFS found Bankok")
				return
			}

			if !visited.contains(destination) {
				self.dfs(start: destination, visited: visited)
			}
		}
	}
}

adjList.dfs(start: "PHX")

print("==================")