Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 85

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

(A) & thetha; (n)
(B) & thetha; (м)
(С) & thetha; (m + n)
(D) & thetha; (мн)

Ответ: (с)
Объяснение: Количество связанных компонентов в неориентированном графе можно просто рассчитать, используя BFS или DFS . Наилучшая временная сложность BFS и DFS — O (m + n).

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2008 | Вопрос 85

0.00 (0%) 0 votes