Учитывая ориентированный граф и некоторые его узлы, как обрезать узлы, которые не могут достичь ни одного из заданных узлов. (Я называю это листовыми компонентами, но не уверен, что это правильный термин)
Существуют ли какие-либо известные алгоритмы, решающие это эффективно?
Было бы идеально, если бы вы указали для него исходный код Java Open.
Спасибо.
Запустите поиск в ширину или поиск в глубину, начиная с заданного набора узлов, и отметьте все узлы, которые пересекает поиск. После этого все непомеченные узлы недоступны из заданного набора узлов и могут быть удалены. Если n — количество вершин, а m — количество ребер, это решит вашу проблему за O(n + m).
Лично я предпочитаю Tinkerpop Blueprints в качестве основной библиотеки для обработки графов в JVM/Java/Scala. .
Если я вас правильно понял, вам нужно найти сильно связанные компоненты, которые можно найти в O (n + m) раз, выполнив 2 поиска в глубину.
