Для чего используются сильно связанные компоненты?
Я нашел несколько алгоритмов, которые объясняют, как найти сильно связанные компоненты в ориентированном графе, но никто не объясняет, почему вы хотели бы это сделать. Каковы некоторые приложения сильно связанных компонентов?
Ответы
Ответ 1
Вы должны проверить курс Тима Ругардена "Введение в алгоритмы" на Курсере. Для каждого алгоритма он переходит, он объясняет некоторые его применения. Очень полезно и позволяет увидеть значение изучения алгоритмов!
Использование сильно связанных компонентов, о которых я помню, это то, что можно было бы использовать его для поиска групп людей, которые более тесно связаны с огромным набором данных. Подумайте о Facebook и о том, как они рекомендуют людям, которые могут быть вашими друзьями...
Это также можно использовать для просмотра кусков населения. Скажите: "Вау, у этого огромного компонента есть хобби ходить назад и любит есть заплесневелую пиццу!", Это может показать корреляцию. Рекламодатели для заплесневелой пиццы будут использовать эти данные для людей, которым нравится ходить назад. Кто знает!
Ответ 2
Один пример приведен в проверке модели:
Поиск сильно связанного компонента выполняется в явной проверке модели в формальной проверке .
При проверке модели у нас есть машина состояний, представляющая модели нашего программного обеспечения/аппаратного обеспечения, и мы пытаемся доказать временную логику 1 на нем.
Например: Формула EG(p) означает: в графе есть путь, где для каждого состояния - логическая формула p дает true.
Алгоритм для проверки правильности EG (p) на графике (модели) нахождения максимальных сильно связанных компонентов (SCC), а затем проверяя пути, ведущие к нему в графе.
Обратите внимание, что проверка модели широко применяется в отрасли - особенно для проверки правильности аппаратных компонентов.
(1) Важность временной логики для информатики велика, и ее изобретатель Амир Пнуэли получил награду за это!
