Data Structure & Algorithm
3주차 - 그래프 탐색, BFS와 DFS를 직접 구현하며 비교
인접 리스트로 무방향/방향 그래프를 만드는 것부터, Queue로 너비 우선 탐색하는 BFS와 재귀로 깊이 우선 탐색하는 DFS를 각각 구현하고 장단점을 비교. 시간 복잡도는 둘 다 O(V+E).
그래프
하나의 주제로 이어지는 배움의 기록.
2개의 기록 최신순
Data Structure & Algorithm
3주차 - 위상 정렬, 순서 관계와 위상이 같은 개념인 이유
위상 수학의 '위상'이 순서 관계와 일대일 대응한다는 것에서 출발해서, DAG의 모든 간선 (u,v)에서 u가 v보다 앞에 오도록 정렬하는 위상 정렬을 구현하고 장단점을 정리.