그래프

그래프는 정점과 간선으로 이루어진 자료구조로, 여러 개의 정점과 이를 연결하는 간선들로 구성된다. 이를 통해 객체와 객체 간의 관계를 표현할 수 있다.

프로그래밍에서 그래프는 일반적으로 인접 행렬(adjacency matrix)이나 인접 리스트(adjacency list)로 구현된다. 인접 행렬은 2차원 배열로 정점과 간선의 연결 여부를 표현하는 방식이며, 인접 리스트는 연결된 간선들을 리스트 형태로 저장하는 방식이다.

그래프를 인접 행렬로 구현한 예시

그래프를 인접 리스트로 구현한 예시

1: [2, 4]
2: [1, 3, 4]
3: [2, 5]
4: [1, 2, 5]
5: [3, 4]

그래프는 많은 알고리즘의 기반이 되며, 그래프를 탐색하는 방법으로는 DFS와 BFS가 있다.

BFS

BFS(너비 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서부터 거리에 따라 단계별로 탐색해 나가는 방법이다. 즉, 가까운 정점부터 먼 정점까지 차례대로 방문하는 알고리즘이다. 이를 위해서는 큐(queue) 자료구조를 사용한다.

BFS는 다음과 같은 시퀸스로 동작한다

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
• 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS 예제 코드:

from collections import deque

def bfs(graph, start):
    visited = [] # 방문한 노드를 담을 리스트
    queue = deque([start]) # 큐 구현을 위해 deque 라이브러리 사용

    while queue: # 큐가 빌 때까지 반복
        node = queue.popleft() # 큐에서 하나의 원소를 뽑아 출력
        if node not in visited:
            visited.append(node)
            # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            queue += sorted(graph[node] - set(visited))

    return visited

# 그래프를 인접 리스트로 구현한 예시
graph = {
    '1': set(['2', '4']),
    '2': set(['1', '3', '4']),
    '3': set(['2', '5']),
    '4': set(['1', '2', '5']),
    '5': set(['3', '4'])
}

print(bfs(graph, '1'))

출력 결과:

['1', '2', '4', '3', '5']

DFS