Всем привет! Наверное, очень глупый вопрос, но все же =) Изучаю графы,

понял, как работает DFS и BFS.

Зачем они нужны в задаче перебора всех вершин, если мы можем, например, в случае с adjacency list просто пройтись по всем ключам в хэшмапе?

Например,

map[int, set[int]] - adjacency list

Просто перечислить все ключи, которые соответствуют вершинам, они же уникальные.

Или это лишь базовый пример перечисления и DFS/BFS используются в более сложных задачах?

Это два базовых алгоритма обработки графа который используется в других алгоритмах как грубо говоря подпрограмма. Например алгоритм поиска циклов в графе подразумевает обход графа в ширину или глубину с проверкой того что ни одна из вершин которые мы проходим уже не была пройдена ранее

Понял. Получается, в случае задачи, где нужно просто перечислить все вершины в графе, то достаточно обойтись без DFS/BFS, перечислив все ключи в хэшмапе?

Вообще-то странно Потому что эти два алгоритма и есть перечисления всех вершин Ну и рёбер графа, правда в определённом порядке

И ещё непонятно Причём здесь хашмап...

Естественно Если у тебя есть какие-то другие способы перебирать все вершины и тебе не нужен поиск в глубину или в ширину, то ты их можешь не делать

Ну у тебя уже есть все вершины, ты же их хранишь. BFS/DFS про обход в каком то порядке

Во, вот это мне интересно. То есть, если мне не нужен порядок, а достаточно вернуть список всех вершин графа G, а сам граф реализован в виде списка смежности - хэшмапа, ключи - вершины, значения - список соседних вершин map[int, set[int]] то хватит перебора всех ключей за O(E)?

Да хватит перебора всех ключей за O(|V|). Буквой Е ребра обычно обозначаются