우선 순위 지정 DAG

DAG를 배열로 저장했습니다. 상위 노드가 가장 높은 우선 순위를 가지며 모든 리프 노드가 가장 낮은 우선 순위를 갖는 방식으로 DAG에 우선 순위를 할당하려면 어떻게해야합니까?우선 순위 지정 DAG

A  # A -> B,C      # A  
/\  # B -> D  ----->   # B C //can be used in parallel 
    C B  # C -> E      # D 
    \ \ # D -> E      # E 
    \ D # E ->        
    \/
    E

내가 부모와 내가 DAG로 사용하고있는 배열에 저장 아이들 모두가

다음으로 나는 DAG가있는 경우.

Topological Sort는 선형 목록을 반환합니다. A,C,B,D,E 전용.

출처

2015-01-13 SMUsamaShah

코드와 시도한 것을 보여줄 수 있습니까? [ask]를 읽어주십시오 –

@EngineerDollery DAG에 따라 작업을 예약하려고합니다. 첫 번째 작업이 먼저 실행되어야합니다. 나는 일자리, 그 부모와 자식을지도에 다른 것들을 포함하여 저장하고있다. 예에서 보여준대로 A와 C가 모두 완료된 경우에만 D를 실행하는 방법을 알지 못합니다. – SMUsamaShah

당신이 찾고있는 것은 topological ordering입니다. DAG에서 노드를 정렬하여 각 부모 앞에 노드가 나타나지 않도록하는 방법이라고 생각합니다. 다행히도 토폴로지 순서는 DAG의 단순 DFS를 기반으로하는 알고리즘을 비롯하여 다양한 토폴로지 정렬 알고리즘을 사용하여 매우 효율적으로 (선형 시간으로) 찾을 수 있습니다.

희망이 도움이됩니다.

출처

2015-01-13 17:11:41 templatetypedef

예, 찾고 있던 토폴로지 순서입니다. 고맙습니다! – SMUsamaShah

많은 번거 로움없이 쉽게 추가 할 수있는 라이브러리가 있습니까? 현재 Map은 입력 및 출력 링크를 포함하여 Objects를 저장하기 위해 사용하고 있습니다. – SMUsamaShah

@ LifeH2O 내 머리 꼭대기에서 그런 라이브러리가 있는지 모르겠다.하지만 하나도 없다고해도 이러한 알고리즘은 코딩하기가 쉽다. 각 노드에서 시작하여 그래프를 통해 DFS를 수행하고 처리를 마친 순서대로 노드를 나열하십시오. 그런 다음 순서를 바꾸어 토폴로지 순서를 되돌립니다. – templatetypedef

우선 순위 지정 DAG

답변

관련 문제