Tarjan 알고리즘을 활용한 그래프의 연결성 분석
연결성 문제와 Tarjan 알고리즘의 역할
그래프 이론에서 우리는 다양한 연결성 문제를 다루게 된다. 방향 그래프에서는 강결합 성분(SCC)을 찾는 문제가 있으며, 무방향 그래프에서는 절단선(bridge), 절단점(cut vertex), 그리고 이들을 기반으로 한 이중 연결 성분(biconnected components) 분석이 중요하다. 이러한 문제들에 대해 Tarjan 알고리즘은 깊이 우선 탐색(DFS ...
9월 26일 15:02에 게시됨