연결성분 검사(connected component)

연결 성분 검사 connected component

최대로 연결된 부분 그래프를 말한다. 즉, 연결된 그래프들 끼리 묶는 것을 말한다.

Untitled 8 2.png

연결성분을 찾기 위해 bfs,dfs를 이용할 수 있다.

  1. 방문되지 않은 임의의 정점을 선택
  2. 선택한 정점을 기준으로 탐색 수행

위 과정의 반복을 통해서 연결성분을 검사할 수 있다.

구현

find_connected_component 가 1번 과정을 수행하면서 2번을 수행해줄 dfs 를 호출하면서 검사를 한다.
dfs 그중에서도 재귀를 이용한 방법으로 구현했다.
find 함수에서 dfs가 호출되면 연결된 노드 끼리 group을 만들어서 반환한다.

def find_connected_component(graph):
    visited =set()
    groupList=[]
    for vtx in graph:
        if vtx not in visited:
            groupList.append(dfs(graph,vtx,visited))

def dfs(graph,vtx,visited):
    group=[]
    visited.add(vtx)
    group.append(vtx)
    for vtx in graph[vtx]:
        if vtx not in visited:
            group.extend(dfs(graph,vtx,visited))
    return group

2차원배열 연결성분

2차원 배열에서 연결성분이 필요한 문제가 많다

def find_connected_components(grid):
    def dfs(r, c, component):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0 or visited[r][c]:
            return
        visited[r][c] = True
        component.append((r, c))
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            dfs(r + dr, c + dc, component)

    rows, cols = len(grid), len(grid[0])
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    components = []

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not visited[r][c]:
                component = []
                dfs(r, c, component)
                components.append(component)

    return components

# 2차원 배열을 정의합니다.
grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 1, 1, 1]
]

# 연결성분을 찾습니다.
connected_components = find_connected_components(grid)

# 결과를 출력합니다.
for i, component in enumerate(connected_components):
    print(f"Connected Component {i + 1}: {component}")

관련 문제로는 백준 17472번 - 다리 만들기2#각 섬을 노드로 표현 이 있다.

관련글