Базовые алгоритмы на графах

Выберите верные утверждения

• DFS - обход в глубину

• BFS - обход в глубину

• DFS - обход в ширину

• BFS - обход в ширину

Асимптотика алгоритма BFS и DFS

Классическим BFS-ом можно искать кратчайшее расстояние между вершинами за O(N + M) на:

• Неориентированных взвешенных графах

• Ориентированных взвешенных графах

• Неориентированных невзвешенных графах

• Ориентированных невзвешенных графах

DFS-ом можно искать кратчайшее расстояние между вершинами на:

• Невзвешенном дереве

• Взвешенном дереве

• Неориентированный невзвешенный ацикличный граф

• Неориентированный взвешенный ацикличный граф

BFS ищет кратчайшее расстояние

• От стартовой вершины до всех достижимых

• Между всеми парами вершин в графе

Классический DFS реализован на

• queue

• deque

• set

• Ничего из перечисленного

Классический BFS реализован на

• queue

• deque

• set

• Ничего из перечисленного

В какие вершины необходимо запуститься алгоритмом DFS, чтобы обойти весь граф (множественный ответ).

• 1, 5

• 2, 6, 7

• 1, 5, 7

• 1, 2, 3

Выберите все двудольные графы

• 
• 
• 
• 

В дереве всегда нет циклов?

• Да

• Нет