Обходы графа и их применения

Обходы

• DFS
• BFS

Применения

• Поиск компонент связности
• Раскраска графа в два цвета
• Поиск циклов
• Остовное дерево
• Проверка принадлежности вершины кратчайшему пути
• Кратчайший цикл в ориентированном графе
• Топологическая сортировка
• Компоненты сильной связности
• Конденсация