반응형 [알고리즘] Week 6: 고급 그래프 알고리즘 - 강한 연결 요소와 위상 정렬 Day 1: 강한 연결 요소 (Strongly Connected Components, SCC)강의 내용:강한 연결 요소의 개념강한 연결 요소란 무엇인가?그래프의 SCC를 찾는 중요성 및 응용 사례강한 연결 요소 탐색 알고리즘코사라주 알고리즘 (Kosaraju's Algorithm)타잔 알고리즘 (Tarjan's Algorithm)실습:간단한 예제 그래프에서 SCC 찾기# 코사라주 알고리즘을 사용한 SCC 찾기from collections import defaultdictclass Graph: def __init__(self, vertices): self.graph = defaultdict(list) self.V = vertices def add_edge(self, u,.. 2024. 6. 2. [알고리즘] 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'.. 2023. 10. 5. 이전 1 다음 반응형
