Алгоритми та структури даних · Senior · Запитання 34 з 75
Що обчислює алгоритм Тарджана або Косараджу?
- 1Найкоротші шляхи з від'ємними вагами ребер
- 2Максимальний потік між двома вершинами
- ✓Правильна відповідь: Компоненти сильної зв'язності орієнтованого графа
Пояснення
Компонента сильної зв'язності - група, де кожна вершина досяжна з кожної. Обидва алгоритми працюють за O(V + E) на DFS. Стягування таких компонент перетворює будь-який орієнтований граф на DAG, що корисно для аналізу залежностей.