반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 10: 위상 정렬 (Topological Sorting) 위상 정렬 (Topological Sorting)위상 정렬은 유향 비순환 그래프(DAG, Directed Acyclic Graph)의 정점을 순서대로 나열하는 방법입니다. 이 순서는 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 나오는 순서를 의미합니다. 위상 정렬은 주로 작업 스케줄링, 컴파일러에서의 심볼 테이블 생성 등에 사용됩니다.위상 정렬의 주요 특징DAG: 위상 정렬은 반드시 유향 비순환 그래프에서만 가능합니다.순서: 정점 u에서 정점 v로 가는 모든 경로에 대해 정점 u는 정점 v보다 먼저 나옵니다.위상 정렬의 구현 방법Kahn's Algorithm: 진입 차수를 이용한 위상 정렬DFS 기반 알고리즘: 깊이 우선 탐색을 이용한 위상 정렬Kahn's AlgorithmKahn's Al.. 2024. 8. 1. [알고리즘] 9. 기타 그래프 이론 Index 1. 서로소 집합 자료구조 2. 서로소 집합을 활용한 사이클 판별법 3. 최소 신장 트리(크루스칼 알고리즘) 4. 위상 정렬 5. 추천 문제 6. 참고자료1. 서로소 집합 자료구조Disjoint Sets- 공통 원소가 없는 두 집합 서로소 집합 자료구조(= Union Find)- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조- 두 종류의 연산을 지원- - Union: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산- - Find: 특정한 원소가 속한 집합이 어떤 집합인지- 연결성을 통해 집합의 형태를 확인 (동작 과정)1) Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 - A와 B의 루크 노드 A', B'를 각각 찾기 - A'를 B'.. 2024. 7. 20. 이전 1 다음 반응형
