구성 요소 간의 종속성을 찾는 데 사용할 알고리즘은 무엇입니까?

Question

빌드 스크립트에서 우리는 애플리케이션을 구성 요소로 분리했습니다.

시나리오는 다음과 같습니다.

모든 구성 요소는 하나 이상의 구성 요소에 의존 할 수 있습니다.

예 : 우리는 Component1에서 Component12까지 가지고 있습니다.

구성 요소 1은 구성 요소 2와 구성 요소 3에 종속됩니다.

구성 요소 4

난 다음이 순서 컴포넌트 2, component3, 컴포넌트 1, component6 및 component4 구축해야 종속성 컴포넌트 1과 component4을 구축하는 스크립트에서 지정하는 경우 컴포넌트 2와 component6에 따라 다릅니다.

종속성을 더 잘 찾고 어떤 구성 요소도 두 번 실행하지 않아도되는지 확인하는 데 유용한 알고리즘입니다.

Answer 1

종속성 그래프를 조정 한 다음 topological sorting을 사용하여 컴파일 순서를 결정할 수 있습니다.

Answer 2

너비 우선 탐색을 사용하여 그래프를 탐색하고 모든 새 노드를 목록에 추가하십시오. 현재 노드가 이미 목록에 있으면 해당 분기를 중단합니다. 마지막에는 목록에서 역순으로 구성 요소를 작성하십시오.

편집 : 적절하게 카페인 처리되지 않았습니다. soulcheck이 제안한대로 토폴로지 정렬을 사용합니다. 내 솔루션이 작동하지 않을 수도 있습니다.