Cycle Detection Algorithm
방향 그래프가 주어졌을 때 종종 이 그래프 내에서 \(Cycle\)의 존재 유무를 확인해야 할 때가 있다. 이 글에서는 방향 그래프 내에서 싸이클의 존재 유무를 알아내는 알고리즘을 소개하려 한다. 기본적인 알고리즘 \(Cycle\)의 정의를 한번 생각해 보자. \(Cycle\)이란 정점 \(u\)에서 시작해 어떠한 경로를 지나 다시 \(u\)로 돌아오는 경로가 있다면 이를 \(Cycle\)이라고 한다. 그리고 그래프 내에 이러한 \(Cycle\)이 한개라도 있다면 \(Cycle\)이 존재하는 그래프가 된다. 그렇다면 특정한 시작 정점 \(u\)를 잡고 \(dfs\)를 실행해 다시 시작정점 \(u\)로 돌아오는 경로가 있는지 확인하는 알고리즘을 만든 뒤 모든 정점에 대해 해당 알고리즘을 실행하면 \(Cyc..
Algorithm/Graph & Tree
2016. 11. 14. 11:03
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Binary Search
- graph
- Data Structure
- Sqrt Decomposition
- brute force
- max flow
- disjoint set
- greedy
- DP
- bipartite matching
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함