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

Вопрос по кодированию графа — все пути от источника к цели (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), поскольку в худшем случае нам придется сложить все пути внутри нашего результата, который затем возвращается из нашей функции.