알고리즘

그래프(1) - DFS, BFS, 위상정렬, 연결성분, 강연결성분

haong_ 2025. 4. 29. 15:46

그래프의 기본

G =(V, E)  

  • 그래프 G는 정점(Vertex)와 간선(Edge)으로 구성된다
  • V: 정점(vertex)의 집합
  • E: 간선(edge)의 집합 

그래프 구현 방법

인접 행렬 

 

  • 정점을 2차원 배열로 표현
  • 행과 열에 해당하는 두 정점 사이에 간선이 있으면 1(또는 가중치), 없으면 0
  • 공간복잡도 O(V^2) 정점수가 많으면 메모리 낭비 
  • 특정 두 정점간 연결 여부를 O(1)로 확인 
정점: 0, 1, 2
간선: (0-1), (1-2)

인접 행렬:
[
 [0, 1, 0],
 [1, 0, 1],
 [0, 1, 0]
]

 

인접 리스트

  • 각 정점마다 연결된 정점 리스트를 별도로 저장
  • 공간복잡도 O(V + E) (간선 수 만큼 메모리 사용 > 희소 그래프에 적합)
  • 정점마다 연결된 간선만 확인해 효율적임 
0: [1]
1: [0, 2]
2: [1]

그래프의 순회 

깊이 우선 탐색 알고리즘 (DFS)

 

  • 한 정점에서 시작해서 가능한 깊게 탐색하다가 더 이상 진행할 수 없으면 다시 되돌아오면서 탐색하는 방식
  • 스택(Stack) 자료구조를 사용해 구현하거나, 재귀 호출로 구현할 수 있음

 

처리과정 

 

  1. 시작 정점을 스택에 넣고 방문 표시
  2. 스택에서 정점을 꺼낸 후
    • 아직 방문하지 않은 인접 정점을 스택에 추가
  3. 스택이 빌 때까지 반복

 

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            # 인접 정점을 스택에 추가 (뒤에서 꺼내기 때문에 reversed)
            stack.extend(reversed(graph[node]))

# 예시
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1],
    4: [2]
}

dfs(graph, 0)
# 0 1 3 2 4

너비 우선 탐색 알고리즘 (BFS)

 

  • 시작 정점에서 가까운 정점부터 차례로 탐색하는 방식
  • 큐(Queue) 자료구조를 사용해 구현

 

처리과정 

 

  1. 시작 정점을 큐에 넣고 방문 표시
  2. 큐에서 정점을 꺼내고
    • 아직 방문하지 않은 인접 정점을 큐에 추가
  3. 큐가 빌 때까지 반복

 

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            queue.extend(graph[node])

# 예시
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1],
    4: [2]
}

bfs(graph, 0)
# 0 1 2 3 4

그래프 순회 응용

위상 정렬(Topological  Sort)

개념

 

  • 사이클이 없는 방향 그래프(DAG) 에서 모든 간선의 방향을 거스르지 않게 정점들을 나열하는 방법
  • 주로 선행 조건이 있는 작업들의 실행 순서를 결정할 때 사용

특징

 

  • 여러 가지 정렬 결과가 있을 수 있음 (정답이 하나만 존재하지 않음)
  • DFS 또는 진입차수(Indegree) 기반 방법으로 구현

 

과정 (DFS 기반) 

 

  1. DFS를 수행한다
  2. 모든 자식 정점(선행해야 할 작업) 을 다 방문한 후,
    • 즉, 더 이상 방문할 곳이 없을 때, 해당 정점을 스택에 삽입
    • (단순 방문순서가 아니라, 선행작업이 다 끝난 뒤 스택에 push하는 것)
  3. DFS가 끝난 후 스택을 역순으로 꺼내면 위상 정렬 결과가 됨
    • 이 순서는 각 정점이 선행 조건을 모두 충족한 상태에서 수행할 수 있는 순서

예시 

5 → 2 → 3 → 1
4 → 0
4 → 1
5 → 0

 

 

 

구분 내용
DFS 방문 순서 5 → 2 → 3 → 1 → 0 → 4
DFS 순서에 따라 스택에 쌓인 순서 (push 순서) 1 → 3 → 2 → 0 → 5 → 4
스택에서 pop한 순서 (위상 정렬 결과) 4 → 5 → 0 → 2 → 3 → 1

 

 연결 성분(Connected Component)

 

  • 무방향 그래프에서 임의의 두 정점 사이에 경로가 존재하는 최대 부분 그래프
  • DFS 또는 BFS로 연결된 모든 정점을 찾으면 하나의 연결 성분

과정

 

  1. 전체 정점을 돌면서 방문하지 않은 정점에 대해 탐색 시작
  2. 탐색을 마치면 하나의 연결 성분 완성
  3. 모든 정점을 처리할 때까지 반복
def connected_components(graph):
    visited = set()
    components = []

    def dfs(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, component)

    for node in graph:
        if node not in visited:
            component = []
            dfs(node, component)
            components.append(component)
    
    return components

# 예시
graph = {
    0: [1],
    1: [0],
    2: [3],
    3: [2],
    4: []
}

print(connected_components(graph))
# [[0, 1], [2, 3], [4]]

 

 

강연결 성분(Strongly Connected Component, SCC)

 

  • 방향 그래프에서 임의의 두 정점 사이에 양방향 경로가 존재하는 최대 부분 그래프

과정

 

  1. 원래 그래프에서 DFS를 수행하여 방문 완료 순서를 기록
  2. 그래프의 모든 간선을 반전(Transpose)한 새로운 그래프를 만든다
  3. 방문 완료 순서의 역순으로 반전 그래프에서 DFS를 다시 수행
  4. DFS를 수행할 때 방문하는 정점들이 하나의 강연결 성분을 이룸

 

예시

1 → 2 → 3 → 1
4 → 5
5 → 6 → 4

 

여기서 강연결 성분은:

  • {1, 2, 3} (서로 서로 갈 수 있음)
  • {4, 5, 6} (4→5→6→4 순환)
  • (나머지 단독 정점들은 자기 혼자 강연결 성분)
저작자표시