선택 심화: 단절점·low·이중 연결 성분

DFS 발견 순서와 되돌아갈 수 있는 조상으로 취약한 연결을 찾습니다.

정점 하나가 고장 나면 연결이 끊어지는지 알고 싶습니다. 목표는 단절점과 이중 연결의 정확한 뜻을 알고, DFS의 low 값이 탐지하는 경계를 이해하는 것입니다. 그래프·DFS·재귀를 먼저 학습하세요.

개념과 약속

단절점은 제거하면 연결 성분 수가 늘어나는 정점입니다. 단순히 서로 다른 두 경로가 있다는 말만으로 정점 이중 연결을 정의할 수 없습니다. 두 경로는 시작·끝을 제외한 내부 정점을 공유하지 않아야 정점 하나의 제거를 견딥니다. 간선 이중 연결은 간선 제거를 기준으로 하는 별도 개념입니다.

DFS discovery[v]는 첫 발견 번호입니다. low[v]는 자기 발견 번호도 포함한 최솟값입니다. v에서 DFS 트리의 자손 쪽으로 내려간 뒤, 부모로 돌아가는 트리 간선을 제외한 역방향 간선을 최대 한 번 써서 만날 수 있는 조상의 발견 번호를 함께 비교합니다. 역방향 간선을 쓰지 못하면 자기 번호가 기본값으로 남습니다. 모든 방향의 간선을 자유롭게 반복해서 얻는 일반 도달 가능성 번호는 아닙니다.

비루트 v의 자식 w에서 low[w] >= discovery[v]이면 w 쪽이 v보다 위로 우회하지 못해 v가 단절점입니다. 등호일 때도 우회가 v까지만 닿으므로 v를 제거하면 끊어집니다. 루트는 DFS 자식이 둘 이상일 때만 단절점입니다. 인접 목록의 이웃 수인 차수와 DFS 자식 수는 다릅니다.

간선 스택에 방문 간선을 기록하다 위 경계에서 묶음을 꺼내 이중 연결 블록을 만듭니다. 이 구현은 단순 무방향·대칭 인접 목록만 허용합니다. 다중 간선·자기 고리는 거부하고, 다리는 한 간선 블록으로 반환하며 고립 정점은 간선 블록에 포함하지 않습니다. 이 작은 예제 코드를 큰 그래프에서 재귀 깊이 검토 없이 사용하지 마세요.

손으로 상태 추적하기

A,B,C 삼각형과 C—D 꼬리입니다. 이웃 순서에 따라 발견 A=0,B=1,C=2,D=3입니다.

정점	low	이유
C	0	C→A 역방향 간선
B	0	자식 C의 low 전달
D	3	부모 C 이외의 우회 없음

D의 low=3 ≥ C의 발견 2라 C가 단절점입니다. 삼각형은 한 블록, C—D는 다리 블록입니다. D는 우회 간선이 없으므로 자기 발견 번호 3이 low로 남습니다.

아래는 바로 위 그래프와 코드의 이웃 순서 그대로 끝까지 따라간 과정입니다. AB는 스택에 저장한 방향 있는 쌍 (A,B)의 짧은 표기이며, 원래 무방향 간선의 방향을 새로 정한다는 뜻은 아닙니다. 스택 왼쪽은 바닥, 오른쪽은 맨 위입니다.

사건	발견·low 변화	사건 뒤 간선 스택	블록·단절점 판단
A 첫 방문	발견 A=0, low A=0	`[]`	루트 자식 0
A에서 미방문 B로 내려감	AB push, B 발견=1·low=1	`[AB]`	A의 DFS 자식 1
B에서 미방문 C로 내려감	BC push, C 발견=2·low=2	`[AB,BC]`	B→A는 부모 간선이라 건너뜀
C에서 이미 발견한 조상 A를 만남	CA push, low C=min(2,0)=0	`[AB,BC,CA]`	부모 B가 아닌 역방향 간선
C에서 미방문 D로 내려감	CD push, D 발견=3·low=3	`[AB,BC,CA,CD]`	C→B는 부모 간선이라 건너뜀
D에서 C로 복귀	low C=min(0,3)=0	`[AB,BC,CA]`	3≥2이므로 CD를 pop해 다리 블록; 비루트 C가 단절점
C에서 B로 복귀	low B=min(1,0)=0	`[AB,BC,CA]`	`0<1`이므로 아직 블록을 꺼내지 않음
B에서 A로 복귀	low A=min(0,0)=0	`[]`	0≥0이므로 CA,BC,AB까지 pop해 삼각형 블록; 루트 A의 자식은 1이므로 단절점 아님
A의 다음 이웃 C 확인	C는 이미 발견한 자손	`[]`	같은 무방향 간선을 다시 push하지 않고 탐색 종료

각 트리 간선은 자식을 처음 방문하기 직전에 push합니다. 역방향 간선은 지금 정점보다 먼저 발견된 조상에게 갈 때만 push합니다. 복귀 때 low[자식] >= discovery[부모]이면 마지막 트리 간선까지 pop해 한 블록으로 묶습니다. 재귀 호출이 끝났다고 간선 스택을 매번 비우지는 않습니다. CA·BC가 B 복귀까지 남아야 삼각형이 같은 블록이 됩니다.

루트 예외도 실제 상태로 확인할 수 있습니다. A—B와 A—C만 있는 그래프에서 A의 이웃을 B,C 순서로 읽으면 B 방문·복귀 뒤 자식은 1, C 방문·복귀 뒤 2입니다. 둘 사이를 잇는 간선이 없으므로 A를 지우면 B와 C 두 성분이 남습니다. 따라서 두 번째 복귀 때 A를 단절점에 넣습니다. 반면 위 삼각형에서는 B 아래에서 C를 먼저 발견해 A의 차수는 2여도 DFS 자식은 B 하나입니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

긴 코드를 읽는 문법·상태 준비

visit은 biconnected_components 안에서 정의한 중첩 함수입니다. 바깥 함수의 discovery, low, parent, edge_stack, blocks, cuts를 참조하며, 재귀 호출들도 같은 사전·목록·집합을 공유합니다. 이렇게 바깥 상태를 참조하는 함수 관계를 클로저라고 합니다. low[vertex] = ...는 사전의 항목을 바꾸고 edge_stack.append(...)는 목록의 내용을 바꾸므로, 바깥 변수 이름 자체를 새 값에 재대입하는 nonlocal 선언은 여기서 필요하지 않습니다.

반면 children은 매 visit(vertex) 호출마다 새로 0부터 시작하는 지역 변수입니다. 미방문 이웃을 재귀로 처음 방문할 때만 증가하므로 DFS 자식 수가 됩니다. 재귀 호출 스택에는 A→B→C→D의 아직 끝나지 않은 함수 호출이 쌓이고, edge_stack에는 아직 블록으로 확정하지 않은 간선이 쌓입니다. 두 스택은 내용도 꺼내는 조건도 다릅니다.

parent.get(vertex)는 루트처럼 부모 항목이 없을 때 None을 주어 KeyError를 피합니다. 정규화 출력의 tuple(sorted(edge))는 AB와 BA를 같은 표기 순서로 만들 뿐, 실제 DFS의 이웃 순서를 바꾸지 않습니다.

def biconnected_components(graph):
    vertices = set(graph)
    neighbor_sets = {vertex: set(neighbors) for vertex, neighbors in graph.items()}
    for vertex, neighbors in graph.items():
        if len(neighbors) != len(neighbor_sets[vertex]) or vertex in neighbor_sets[vertex]:
            raise ValueError("simple undirected graph required")
        for neighbor in neighbors:
            if neighbor not in vertices or vertex not in neighbor_sets[neighbor]:
                raise ValueError("symmetric adjacency required")
    discovery, low, parent, edge_stack = {}, {}, {}, []
    blocks, cuts = [], set()
    def visit(vertex):
        discovery[vertex] = low[vertex] = len(discovery)
        children = 0
        for neighbor in graph[vertex]:
            if neighbor not in discovery:
                parent[neighbor] = vertex
                children += 1
                edge_stack.append((vertex, neighbor))
                visit(neighbor)
                low[vertex] = min(low[vertex], low[neighbor])
                if low[neighbor] >= discovery[vertex]:
                    if vertex in parent or children > 1:
                        cuts.add(vertex)
                    block = []
                    while edge_stack:
                        edge = edge_stack.pop()
                        block.append(edge)
                        if edge == (vertex, neighbor):
                            break
                    blocks.append(block)
            elif neighbor != parent.get(vertex) and discovery[neighbor] < discovery[vertex]:
                edge_stack.append((vertex, neighbor))
                low[vertex] = min(low[vertex], discovery[neighbor])
    for vertex in graph:
        if vertex not in discovery:
            visit(vertex)
    return blocks, cuts


graph = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}
blocks, cuts = biconnected_components(graph)
normalized = sorted(sorted(tuple(sorted(edge)) for edge in block) for block in blocks)
print(normalized)
print(sorted(cuts))

실행 결과:

[[('A', 'B'), ('A', 'C'), ('B', 'C')], [('C', 'D')]]
['C']

왜 맞고 언제 끝나는가

역방향 간선은 현재 서브트리에서 우회해 연결되는 조상의 발견 번호를 low에 반영합니다. 자식의 low가 부모보다 앞선 조상에 닿지 못하면 그 부모를 제거했을 때 분리됩니다. 루트는 위쪽 조상이 없으므로 자식 수라는 별도 조건이 필요합니다. 각 정점은 한 번 발견되고 각 간선은 유한하게 처리되어 종료합니다.

비용과 적용 범위

입력 검증을 위해 이웃 목록을 집합으로 한 번 변환합니다. 딕셔너리·집합의 일반적인 평균 O(1) 조회 모델에서 전처리와 DFS를 합쳐 시간 O(V+E), 발견·low·이웃 집합·간선 스택 O(V+E) 공간입니다. 원래 목록은 DFS의 이웃 순서를 유지하는 데 사용합니다. 대칭 여부를 이웃 리스트에서 매번 선형 검색하면 이 전처리 시간 보장을 잃습니다. 재귀 깊이는 최악 O(V)입니다. 코드 길이가 길어졌다면 먼저 손으로 삼각형+꼬리의 번호·low·간선 스택을 완성한 뒤 전체 코드를 읽으세요.