2JINISHAPPY 2JINISHAPPY

DAG는 Topological Sort, Strongly Connected Component 등을 정의할 때 자주 사용되는 자료구조로 사이클이 존재하지 않는 방향 그래프 를 의미한다 DAG를 이해하기 위해 Directed graph G가 cycle이 있다 ↔ G의 DFS Tree가 back edge를 가지고 있다 이러한 성질들은 서로 필요충분조건을 만족한다는 사실을 알 필요가 있다 1️⃣ ⬅ (G의 DFS Tree가 back edge를 가지고 있다면 G에는 cycle이 존재한다) : 그래프 G에서 임의의 정점 u와 v에 대해 back edge(v,u)가 존재한다고 가정한다(위의 그림). 그러면 u ➡ ... ➡ v ➡ u로의 cycle이 존재한다 2️⃣ ➡ (Directed Graph G가 cycle이 ..

우리는 종종 Connected Component에 대해 들어보곤 한다. 주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포함해야하며, 하나라도 더 추가한 순간 disconnected해야한다)를 의미한다. 여기에서 사이클에 대한 조건을 추가한 개념이 Biconnected Component(BCC)라고 할 수 있다. 위의 그림과 같은 무방향 간선 (연결) 그래프가 있다고 가정하자. 이 상태에서 vertex A 및 A와 연결된 모든 edge를 삭제하면 그래프는 (D,G,H)와 (B,C,E,F,I,J)로 분리된 disconnected graph가 된다. 이렇게 해당 그래프에서..