Задача: 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 {
    /**
     * @param Integer[][] $graph
     * @return Integer
     */
    function shortestPathLength($graph) {
        $n = count($graph);
        if ($n == 1) return 0;
        
        $endingMask = (1 << $n) - 1;
        $seen = array_fill(0, $n, array_fill(0, $endingMask, false));
        $queue = [];
        
        for ($i = 0; $i < $n; $i++) {
            $queue[] = [$i, 1 << $i];
            $seen[$i][1 << $i] = true;
        }
        
        $steps = 0;
        while (!empty($queue)) {
            $nextQueue = [];
            foreach ($queue as [$node, $mask]) {
                foreach ($graph[$node] as $neighbor) {
                    $nextMask = $mask | (1 << $neighbor);
                    if ($nextMask == $endingMask) return 1 + $steps;
                    if (!$seen[$neighbor][$nextMask]) {
                        $seen[$neighbor][$nextMask] = true;
                        $nextQueue[] = [$neighbor, $nextMask];
                    }
                }
            }
            $steps++;
            $queue = $nextQueue;
        }
        
        return -1;
    }
}

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