연결이 끊어진 DAG의 토폴로지 정렬 순서

Question

숫자 0, 1, 2가 유성 비순환 그래프의 노드이고 우리의 가장자리가 하나만있는 경우 : 1 -> 2입니다. 올바른 주문은 다음과 같습니다.

1,2,0 
0,1,2 
1,0,2 

정확합니까? 나는 마지막 순서에 대해서만 확신하지 못합니다. 1,0,2 유효합니까?

Answer 1

네, 맞습니다.

definition에 따르면, 위상 주문을위한 유일한 조건은 모든 방향 가장자리 u->v에 대한 유 V 앞에 와야한다는 것입니다. V 전에 단지 와야했다되지 않습니다.

작업을 나타내는 정점을 고려 수행 할 준비가되었다고 말하십시오. 0은 타이를, 1은 양말을, 2는 신발을 신습니다. 따라서 1은 2 (1-> 2) 앞에옵니다. 보시다시피, 당신이 작성한 마지막 주문은 토폴로지상의 순서로 간주 될 수 있습니다 (양말 착용 후 넥타이를 한 후 신발)