트래버스 중 위상 적 정렬?

Question

지향 비순환 그래프를 순회하면서 토폴로지별로 정렬 할 수 있습니까?

내 경우에 해당하는 추가 조건 중 하나는 항상 내 DAG에 들어오는 가장자리가없는 꼭지점 하나가 있다는 것입니다. (내 경우는 하나의 엔트리 파일 만있는 파일 종속성 구조입니다.)

모든 정점을 먼저 찾은 다음 정렬하지 않고 그래프를 가로 지르는 동안 토폴로지별로 정렬 된 목록을 작성할 수 있는지 궁금합니다. 나중에.

Answer 1

당신은 그래프를 통과 수정 DFS를 실행하여 DAG 그래프의 위상 종류를 찾을 수 :

Wikipedia에서 :

위상 정렬을위한 알고리즘은 깊이 우선 검색을 기반으로합니다. 알고리즘은 임의의 순서로 그래프의 각 노드를 순환하여 토폴로지 정렬의 시작 이후 이미 방문한 노드 인 에 도달 할 때 종료되는 깊이 우선 검색을 시작하거나 노드에 나가는 것이 없습니다 가장자리 (즉, 잎 노드) : 당신이 그것을 구글 경우

L ← Empty list that will contain the sorted nodes 
while there are unmarked nodes do 
    select an unmarked node n 
    visit(n) 


function visit(node n) 
    if n has a permanent mark then return 
    if n has a temporary mark then stop (not a DAG) 
    mark n temporarily 
    for each node m with an edge from n to m do 
     visit(m) 
    mark n permanently 
    add n to head of L 

당신은 많은 구현을 찾을 수 있습니다, 하나의 구현 당신은 here을 찾을 수 있습니다.