В чем разница поиска в ширину и поиска в глубину

Что проверяют

Понимаете ли вы, что два обхода отличаются порядком посещения вершин, а отсюда и задачами, для которых подходят. Почти всегда следом просят написать один из них на C# или объяснить, почему BFS находит кратчайший путь, а DFS нет.

Как отвечать

• BFS (в ширину): идёт по уровням, сначала все соседи стартовой вершины, потом соседи соседей. Структура данных Queue<T>. В невзвешенном графе первое попадание в вершину даёт кратчайший путь по числу рёбер;
• DFS (в глубину): уходит по одной ветке до конца и возвращается назад. Структура Stack<T> или рекурсия, то есть стек вызовов. Подходит для поиска циклов, топологической сортировки, компонент связности, перебора с возвратом;
• сложность: обе O(V + E) по времени при списке смежности. По памяти BFS держит весь фронт обхода, вплоть до ширины уровня, а DFS держит текущий путь, вплоть до глубины графа.

Для C# стоит показать каркас: Dictionary<int, List<int>> для графа, HashSet<int> для посещённых, Queue<int> для BFS. Вершину помечайте посещённой в момент постановки в очередь, а не при извлечении, иначе одна вершина попадёт в очередь несколько раз. Чтобы восстановить сам путь, храните словарь «откуда пришли» и пройдите по нему от цели к старту.

Дальше полезно сказать, где BFS заканчивается: во взвешенном графе нужен алгоритм Дейкстры на PriorityQueue<TElement, TPriority>, который есть в .NET начиная с версии 6.

Где спотыкаются

Пишут рекурсивный DFS на графе с сотнями тысяч вершин. В .NET StackOverflowException нельзя перехватить, процесс просто завершается, поэтому на больших данных нужен итеративный вариант с явным Stack<T>.

Забывают про множество посещённых. На дереве это сходит с рук, а на графе с циклом обход зацикливается или обрабатывает вершины многократно.

Говорят, что DFS тоже найдёт кратчайший путь, если дойдёт до цели. Он найдёт какой-то путь, а чтобы получить кратчайший, придётся перебрать все пути, и на плотном графе это уже экспоненциальная работа.