Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 | 31 |
Tags
- qorwns
- AVL 시간 복잡도
- c#
- 백준 1406
- 해시구현
- 자료구조
- Stack 이란
- dfs
- 백준 17779
- 게리멘더링2
- 백준 2447
- 시간 복잡도
- 별 찍기 10
- 구현
- 백준 1158
- ㅣ풀이
- heap
- 5397
- 1764
- 백준
- 백준 17822
- 백준 17471
- 버킷 정렬
- C/C++ 구현
- 조세퍼스 순열
- 해시 구현
- 백준 5397
- 풀이
- 원판 돌리기
- 스택의 특징
Archives
- Today
- Total
홍시홍의 프로그래밍
위상 정렬(사용하는 이유, 특징, 구현, 시간 복잡도) 본문
사용하는 이유
주어진 그래프에서의 진입차수를 이용한 순서를 구하기 위하여
특징
여러가지 위상 정렬 그래프가 나올 수 있다.
구현
위상 정렬을 정렬한 리스트와
진입 차수가 0이 되면 삽입할 큐 2개를 이용하여 구현다
현재 노드와 연결된 간선을 하나하나 제거해주면 진입되는 노드의 진입 차수가 0이 되면 큐에 넣으면서 정렬할 수 있도록 한다.
시간 복잡도
시간 복잡도는 O(V+E) 모든 노드에 대해 모든 간선을 탐색하여야 한다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] 프림 알고리즘(시간 복잡도, 구현방법, 특징) (0) | 2020.06.11 |
|---|---|
| 코사라주 알고리즘(시간복잡도, 구현 방법, 준비 사항) (0) | 2020.06.10 |
| 셸 정렬(정의, 구현방법, 장점 및 시간복잡도) (0) | 2020.06.09 |
| [알고리즘] MST, 최소 스패닝 트리(특징, 구현방법, 시간복잡도) (0) | 2020.05.28 |
| [알고리즘] 정렬의 하한 증명 (0) | 2020.05.27 |
Comments