그래프의 노드의 토폴로지 별 정렬 하위 집합

Question

종속성 집합을 나타내는 큰 그래프가 있습니다. 사용자는 특정 수의 이러한 종속성을 사용하도록 지정할 수 있으며이를 사용하려면 올바른 순서를 알아야합니다 (직접 관련이 없지만 그래프의 다른 노드를 통해 종속 된 종속 노드를 지정할 수도 있음) .

현재 그래프의 토폴로지 종류를 실행하고 사용자가 지정한 노드를 모두 정렬하면이 기능을 구현합니다. 그러나 이것은 최소한의 일종의 종속성을 발생시키지 않으며 다시 돌아가서 불필요한 노드를 제거해야합니다.

노드의 하위 집합의 토폴로지 종류를 찾는 데이 알고리즘이나 알려진 알고리즘을 수행하는 더 좋은 방법이 있습니까?

Answer 1

최적의 솔루션은 종속성을 적절하게 할당하여 사용자가 선택한 노드 만 새 그래프로 구성 할 수 있습니다. 예를 들어, A -> B -> C, 사용자가 A와 C를 선택하면 구성된 그래프는 A -> C입니다. 그런 다음 표준 토폴로지 정렬을 수행합니다.