Я нашел несколько алгоритмов, которые объясняют , как найти сильно связанные компоненты в ориентированном графе, но ни один из них не объясняет , почему вы хотели бы сделать это. Каковы некоторые приложения сильно связанных компонентов?Для чего нужны сильно связанные компоненты?
Вы должны ознакомиться с курсом «Введение в алгоритмы» Тима Ругарддена на Курсера. Для каждого алгоритма он переходит, он объясняет некоторые его применения. Очень полезно, и вы видите ценность изучения алгоритмов!
Использование сильно связанных компонентов, о которых я помню, говорит, что можно использовать его для поиска групп людей, которые более тесно связаны в огромном наборе данных. Подумайте о Facebook и о том, как они рекомендуют людей, которые могут быть вашими друзьями ...
Это также можно использовать для просмотра кусков населения. Скажите: «Вау, у этого огромного компонента есть хобби ходить назад и любит есть заплесневелую пиццу!», Это может показать корреляцию. Рекламодатели для заплесневелой пиццы будут использовать эти данные для людей, которым нравится ходить назад. Кто знает!
Одним из примеров является model checking:
Поиск сильно связный компонент выполняется в явном model checking в formal verification.
В модели проверки - у нас есть конечный автомат, который представляет собой модели нашего программного обеспечения/оборудования, и мы пытаемся доказать, что формулы на нем. temporal logic Формулы на нем.
Например: Формула EG(p) средств: существует путь в графе, где для каждого состояния - логическая формулы p урожайности true.
algorithm for proving if EG(p) is true on a graph (модель) нахождение максимальных сильно связанных компонентов (SCC), а затем проверка путей, ведущих к нему на графике.
Обратите внимание, что проверка модели широко применяется в промышленности - особенно для проверки правильности компонентов оборудования.
(1) Важность временной логики информатики велика, и его изобретатель Amir Pnueli получил награду Тьюринга за это!
Как и большинство математики, это одна из тех вещей, которые кажутся совершенно бесполезными, пока они вам не понадобятся. – trutheality