Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard

У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.

Верните длину кратчайшего пути, который посещает каждый узел. Вы можете начать и закончить в любом узле, вы можете несколько раз посещать узлы и использовать ребра повторно.

Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

👨‍💻 Алгоритм:

1⃣Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов.

2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps.

3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов.

😎 Решение:

class Solution {
    func shortestPathLength(_ graph: [[Int]]) -> Int {
        let n = graph.count
        if n == 1 {
            return 0
        }
        
        let endingMask = (1 << n) - 1
        var seen = Array(repeating: Array(repeating: false, count: endingMask), count: n)
        var queue = [(node: Int, mask: Int)]()
        
        for i in 0..<n {
            queue.append((i, 1 << i))
            seen[i][1 << i] = true
        }
        
        var steps = 0
        while !queue.isEmpty {
            var nextQueue = [(node: Int, mask: Int)]()
            for (node, mask) in queue {
                for neighbor in graph[node] {
                    let nextMask = mask | (1 << neighbor)
                    if nextMask == endingMask {
                        return 1 + steps
                    }
                    if !seen[neighbor][nextMask] {
                        seen[neighbor][nextMask] = true
                        nextQueue.append((neighbor, nextMask))
                    }
                }
            }
            steps += 1
            queue = nextQueue
        }
        
        return -1
    }
}

Ставь 👍 и забирай 📚 Базу знаний