We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Breadth First Search: Shortest Reach
  5. Discussions

Breadth First Search: Shortest Reach

  • omarjalilfierro
     + 0 comments

    This is what I have for swift, but I'm not passing 2 cases becase of performance, what am I doing wrong?

    func bfs(n: Int, m: Int, edges: [[Int]], s: Int) -> [Int] {
    // Write your code here
    var visited = [Int: Int]()
    visited[s] = 0
    var queue = [s]
    
    var dictionary = [Int: [Int]]() 
    
    for edge in edges { 
        dictionary[edge[0], default: [Int]()].append(edge[1])
        dictionary[edge[1], default: [Int]()].append(edge[0])
    }
    
    while !queue.isEmpty {
        let currentNode = queue.removeLast()
        guard let nodes = dictionary[currentNode] else { continue }
        
        for node in nodes {
            if (visited[node] == nil ) {
                visited[node] = visited[currentNode]! + 6;
                queue.append(node)
            } else if (visited[node]! > visited[currentNode]! + 6) {
                visited[node] = visited[currentNode]! + 6;
            }
        }
    }
    
    var result = [Int]()
    for i in 1...n {
        if i == s {
            continue
        } 
        result.append(visited[i] ?? -1)
    }
    
    return result
}