알고리즘/그래프
2020. 6. 22.
Biconnected Component
Biconnected Component (BCC)는 무방향 그래프에서, 다음 조건을 만족하는 정점의 부분집합을 말합니다. 1. 부분집합에서 어떤 정점 하나를 삭제하더라도, 남은 정점들은 서로 연결되어 있다. 2. 이 부분집합에 다른 정점들을 추가하더라도 1을 만족하지 않는다. (1번을 만족하는 최대 크기의 집합이다) 따라서 다음과 같은 무방향 그래프는, 다음과 같이 5개의 BCC로 분리됩니다. 그래프를 이와같이 BCC로 분리하여 하나의 BCC를 하나의 정점으로 대체하면 그래프를 트리로 나타낼 수 있게 됩니다. 일반적인 그래프를 트리로 바꾸고 나면 트리에만 사용할 수 있는 다양한 알고리즘을 사용할 수 있게 됩니다. SCC를 먼저 보신분들은 알겠지만, SCC와 개념이나 코드가 거의 동일합니다. SCC의 무방..
