# 위상 정렬, 사이클 검출

## 위상 정렬

**1. 기초**

사이클이 없는 단방향 그래프면 일단 위상 정렬 의심하기.

간선 하나 탐색해서 뽑아버릴 때마다 indegree 하나씩 빼주고, indegree가 0이 되면 그제야 해당 정점에서 갈 수 있는 다음 정점을 탐색한다.

쉽게 말하여, "**들어올 수 있는 간선 다 찾았으면 다음으로 보낸다.**"

근데 재귀로 역탐색하면 해당 도착지까지 필요한 경로를 위상 정렬과 똑같이 구할 수 있음. 이렇게 하는게 더 간단. ([코드](https://lazyartisan.tistory.com/51)) 모든 정점에 대해 순서를 지켜서 출력해야되는거면 역탐색 재귀 쓰면 안됨.

**2. 경로 역추적**

경로 역추적 (임계경로 문제) : [코드](https://lazyartisan.tistory.com/52)

## 그래프 사이클 검출

* 유향 그래프
  * dfs 하면서 방문하면 traced true, 방문 끝나면 traced false, visited true
  * dfs 도중 visited true인 노드를 방문하면 해당 dfs 분기 끝, traced true인 노드를 방문하면 사이클 존재.
* 무향 그래프 : dfs 하면서 부모가 아닌데 또 방문하게 됐다면 사이클 존재


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.