Graph (powered by adjacency lists) - IsTree

graph.swift

import Foundation

struct Edge<T> where T: Hashable {
    var vertex: Vertex<T>
    var edges: [Edge<T>] = []
}

struct Vertex<T> where T: Hashable {
    let id: Int
    let data: T
}

class Graph<T> where T: Hashable {
    init() {}
    
    private var adjacencies: [Edge<T>] = []
    
    var vertexes: [Vertex<T>] {
        var vertices = [Vertex<T>]()
        for edgeList in adjacencies {
            vertices.append(edgeList.vertex)
        }
        
        return vertices
    }
    
    func add(value: Edge<T>) {
        adjacencies.append(value)
    }
    
    private func isTree(_ edges: [Edge<T>] = [], searched: inout [Int]) -> Bool {
        for i in 0..<edges.count {
            guard !(searched.contains(edges[i].vertex.id) && edges[i].edges.count > 0) else {
                return true
            }
            
            searched.append(edges[i].vertex.id)
            return isTree(edges[i].edges, searched: &searched)
        }
        
        return false
    }
     
    var isTree: Bool {
        
        var searched:[Int] = []
        
        let output = adjacencies.reduce(false) { (accumulated, edges) -> Bool in
            return accumulated || isTree([edges], searched: &searched)
        }
        
        return output
    }
}

let graph = Graph<String>()
let graph2 = Graph<String>()

let v1 = Vertex<String>(id: 1, data: "abc")
let v2 = Vertex<String>(id: 2, data: "def")
let v3 = Vertex<String>(id: 1, data: "ghi")
let v4 = Vertex<String>(id: 2, data: "jkl")

let edge1 = Edge<String>(vertex: v1, edges: [Edge<String>(vertex: v2, edges: [])])
let edge2 = Edge<String>(vertex: v2, edges: [Edge<String>(vertex: v1, edges: [])])
let edge3 = Edge<String>(vertex: v1, edges: [Edge<String>(vertex: v4, edges: [])])

graph.add(value: edge1)
graph.add(value: edge2)
graph.isTree // ✅

graph2.add(value: edge3)
graph2.isTree // ❌