유향 그래프에 단 하나의 토폴로지 정렬이 있는지 확인

Question

유향 그래프에 단 하나의 위상 배열이 있는지 여부를 확인하는 알고리즘에 대한 의사 코드를 작성하려고합니다. 이미 토폴로지 정렬 (DFS 사용)을위한 의사 코드를 생각해 냈습니다.하지만 그다지 도움이되지는 않습니다. 그래프에 싱크대가 없는지 궁금합니다. 하나의 토폴로지 순서가 없습니다 (도움이 될만한가요?).

Answer 1

나가는 가장자리가없는 버텍스에서 시작할 때 가능한 최상의 런타임이 개선되므로 this answer의 개선입니다.

당신의 지시 그래프 N 정점을 가지고 있으며, 당신이 indegree 0 정확히 하나의 시작 정점,

• 마 DFS가있는 경우 (만 시작 정점에) 토폴로지 종류 L을 얻을 수 있습니다.
• L에 정점이없는 경우 일부 정점에 도달 할 수 없거나 (순환의 일부 임) 다른 시작점이 필요합니다 (따라서 여러 토폴로지가 있음). [0,N-2]에서 i를 들어
,
• L[i]에서 L[i+1]에는 가장자리가없는 경우,
  • 반환 거짓.
• 반환 true.

---

또는 칸의 알고리즘을 수정 : 하나 개 이상의 정점 알고리즘이 실행되는 동안, false를 반환 (indegree 0의 정점의) 세트에있는 경우. 그렇지 않으면 true를 반환합니다.