An unweighted graph records which vertices are connected without assigning numerical costs or distances to its edges. A path is therefore evaluated by its number of edges, not by a sum of weights. section 4.1 section 4.2
A practical Swift representation uses:
- An adjacency-list array, where each vertex index stores its incident edges. section 4.1
- An UnweightedEdge containing from and to vertex indices, plus a reversed edge for bidirectional connections. section 4.1
- An UnweightedGraph whose vertices are Equatable values and whose edges use UnweightedEdge. section 4.1
- A convenience addEdge operation that inserts both directions for an undirected connection. section 4.1
Hyperloop network
A city graph connects Seattle to Chicago and San Francisco, then links the remaining cities through similar connections. Asking for the shortest route from Boston to Miami produces Boston > Detroit > Washington > Miami: three edges, regardless of any real-world distance. section 4.1 section 4.2
open class UnweightedGraph<V: Equatable>: Graph {
var vertices: [V] = [V]()
var edges: [[UnweightedEdge]] = [[UnweightedEdge]]() //adjacency lists
public init() {
}
public init(vertices: [V]) {
for vertex in vertices {
_ = self.addVertex(vertex)
}
}
/// This is a convenience method that adds an unweighted edge.
///
/// - parameter from: The starting vertex's index.
/// - parameter to: The ending vertex's index.
public func addEdge(from: Int, to: Int) {
addEdge(UnweightedEdge(u: from, v: to))
}
/// This is a convenience method that adds an unweighted, undirected
edge between the first occurrence of two vertices.
///
/// - parameter from: The starting vertex.
/// - parameter to: The ending vertex.
public func addEdge(from: V, to: V) {
if let u = indexOfVertex(from) {
if let v = indexOfVertex(to) {
addEdge(UnweightedEdge(u: u, v: v))
}
}
}
/// MARK: Implement CustomStringConvertible
public var description: String {
var d: String = ""
for i in 0..<vertices.count {
d += "\(vertices[i]) -> \(neighborsForIndex(i))\n"
}
return d
}
}
Inspect the concrete Swift graph type and its vertex- and index-based edge helpers. section 4.1
extension Graph {
//returns a path to the goal vertex
func bfs(initialVertex: VertexType, goalTestFn:
(VertexType) -> Bool) -> Path? {
guard let startIndex = indexOfVertex(initialVertex)
else { return nil }
// frontier is where we've yet to go
let frontier: Queue<Int> = Queue<Int>()
frontier.push(startIndex)
// explored is where we've been
var explored: Set<Int> = Set<Int>()
explored.insert(startIndex)
// how did we get to each vertex
var pathDict: [Int: EdgeType] = [Int: EdgeType]()
// keep going while there is more to explore
while !frontier.isEmpty {
let currentIndex = frontier.pop()
let currentVertex = vertexAtIndex(currentIndex)
// if we found the goal, we're done
if goalTestFn(currentVertex) {
return pathDictToPath(from: startIndex, to: currentIndex,
pathDict: pathDict)
}
// check where we can go next and haven't explored
for edge in edgesForIndex(currentIndex)
where !explored.contains(edge.v) {
explored.insert(edge.v)
frontier.push(edge.v)
pathDict[edge.v] = edge
}
}
return nil // never found the goal
}
}
Use breadth-first search to find a shortest path by exploring vertices in increasing edge distance. section 4.2
