Вопрос по кодированию графа — все пути от источника к цели (LeetCode)

Описание: Вот пошаговое объяснение задачи о графе, включающей поиск в ширину!

Посетите мою платформу для подготовки к собеседованиям, чтобы изучить закономерности!

📢 Платформа для подготовки к собеседованиям: https://algoswithmichael.com

🎧 Присоединяйтесь к сообществу Discord:   / discord  
💰 Поддержите меня на Patreon:   / michaelmuinos  
🔗Подпишитесь на меня в LinkedIn:   / michael-muinos  
📂Подпишитесь на меня в Github: https://github.com/MichaelMuinos

В этом видео я объясняю популярный вопрос о кодировании графов, заданный в Bloomberg. Для решения этой задачи нам дан двумерный массив, представленный в виде графа, и нам нужно найти все возможные пути от узла 0 до узла n - 1, где n — длина нашего входного массива. Для решения этой задачи мы можем использовать поиск в глубину или поиск в ширину. В данном объяснении мы будем использовать поиск в ширину (BFS), а это значит, что мы должны использовать очередь.

Начиная с узла 0, мы добавляем в нашу очередь список целых чисел, представляющих пути, которые мы прошли до этой точки. По мере того, как мы опрашиваем очередь, последний узел в списке — это узел, с которого мы должны продолжить поиск в ширину. Если последний узел в списке — это узел n - 1, то мы успешно нашли путь от исходной вершины к целевой вершине, и мы добавляем этот список в наш результат.

Временная сложность этого решения составляет O(N^2 * 2^N), где N — количество узлов в нашем графе. 2^N получается из-за того, что для каждого пути и для каждого узла мы можем либо 1) добавить узел в путь, либо 2) не добавлять узел в путь, что приведет к комбинации путей, суммой дающей 2^N. Сложность пространства составляет O(2^N), поскольку в худшем случае нам придется сложить все пути внутри нашего результата, который затем возвращается из нашей функции.