Конечно, давай-ка эту BFS разберём как профи. Сначала забудь про плотную матрицу – используй списки смежности, чтобы обрабатывать только существующие рёбра. Потом упакуй этих соседей в плоский массив с указателем на начало; никаких перераспределений векторов. Используй простой кольцевой буфер для очереди – просто массив с индексами начала и конца, никакого `pop_front`! Если у тебя многоядерная машина, разбей граф на блоки и проведи параллельное расширение границы, потом объедини посещённые вершины с помощью bitmap без блокировок. Так ты просканируешь каждое ребро только один раз, сохранишь хорошую локальность памяти и дашь процессору разогнаться. Попробуй, и увидишь, как время выполнения уменьшится. Готова погружаться?