아크 별 Topological 정렬

Question

정말 약간의 안내가 필요합니다 :방향 별 그래프에서 모든 호를 순서대로 정렬하는 방식으로 정점에 삽입하는 모든 호가 앞으로 오게해야합니다 이 꼭지점에서

Answer 1

위상 정렬에서 아무 것도 변경할 필요가 없습니다. 단지 그것을 사용할 수 있고 후 처리 할 수 ​​있습니다.

의사 코드

높은 수준 :

1. 실행 위상 종류, 그것은 arr [명령 반복]의 각 정점 v에 대한 l
2. 하자, 결과 배열이 arr
3. 가 비어 가장자리 목록을 작성하자 :
   3.1. 각 (v,u)에 E :
   3.1.1. 반환 (v,u) to l
4. l

를 추가이 방법의 장점은 그것을 그냥 사후 처리가 원하는 결과를 얻기 위해 수정하지 않고, 위상 일종의 블랙 박스를 사용할 수있다.

정확성 [증거의 스케치] :
이후 (v,u) 각 에지 - u은 위상 일종의 v 후, 당신이 그것을 인쇄 할 때, 그것은 v을 통해 이루어집니다, 당신은 어떤 정점을 인쇄하기 전에 따라서 (v,u)가 인쇄되어 나타납니다 u에 첨부

복잡성 :
O(|V|+|E|) 위상 정렬 후 처리 [순회 모든 꼭지점 모든 가장자리]의 O(|V|+|E|).

Answer 2

"전통적"위상 정렬은 정점을 정렬하는 반면,이 정렬은 정점을 정렬합니다. 그렇지 않으면 원칙은 동일합니다 ...