7
내 문제는 매우 간단하지만 난 정말 그 이름을 모르는 따라서, 그것은 자신에 의해 해결책을 찾기 어렵다 :의존성 그래프를 "단순화"하는 알고리즘이 있습니까?
A : (
->수단 따라 다름)와 같은 의존성 그래프를 단순화하는 방법 -> B -> C & A -> C
A -> B -> C
A
답변
6
에 당신은 transitive reduction 찾고 있습니다.
알고리즘에 대한 설명은 Transitive Closure and Reduction을 참조하십시오.
다른 그래프입니다. A는 C에 의존하고 B는 "A-> B-> C"는 "단순화"가 아니다. –
첫 번째 그래프는 다음과 같다 : D (A) = {B, C}, D (B) = {C}, D C가 B보다 먼저 수행되어야하기 때문에 그래프 D (A) = {B}, D (B) = {C}, D (C) = {}가 같습니다. – Maxime
@Peter 종속성은 전이 적이라고 생각합니다. 이는 질문자의 목적에 따라 동일합니다. –