방향 그래프에서 역방향과 정방향을 모두 고려하는 이유는 그래프의 연결성을 분석하거나 경로를 탐색할 때 중요한 역할을 합니다.
-
A에서B로 갈 수 있다고 해서 반드시B에서A로 갈 수 있는 것은 아니다. -
강한 연결 요소(SCC)와 약한 연결 요소(WCC) : 방향 그래프에서 강한 연결 요소는 어떤 두 정점 사이에도 서로 도달 가능한 최대 부분 그래프입니다.
이를 파악하기 위해 역방향 그래프를 사용하는 것이 흔합니다. 예를 들어, 코사라주 알고리즘은 먼저 정방향 DFS를 한 뒤, 역방향 그래프에서 다시 DFS를 수행하여 SCC를 찾습니다.
