알고리즘 03 - (기본 패턴 02) - (2) 그래프 탐색, BFS (너비 우선 탐색, Breadth-First Search) 에서 그래프란란?

3 분 소요

BFS에서 그래프란 무엇인가? (수학적 정의)

BFS(너비 우선 탐색, Breadth-First Search)는 그래프(Graph)를 탐색하기 위한 알고리즘입니다.
그래프는 수학적으로 정점(Vertex)과 간선(Edge)의 집합으로 정의됩니다.

Vertex와 Edge의 어원

1. Vertex (정점)

어원:
- Vertex는 라틴어 “vertere”에서 유래했으며, “회전점”, “꼭짓점”을 의미합니다.
- 라틴어에서 “vertere”는 “회전하다(turn)” 또는 “꺾다(bend)”라는 뜻입니다.
- 기하학적으로 다각형, 다면체의 꼭짓점(모서리가 만나는 점)을 의미합니다.
그래프에서의 의미:
- Vertex는 데이터 포인트를 나타내며, 그래프의 각 요소를 연결하는 단위입니다.
- 예: 도시, 사람, 웹 페이지 등.

2. Edge (간선)

어원:
- Edge는 고대 영어 “ecg”에서 유래했으며, “칼날” 또는 “경계선”을 의미합니다.
- 기하학적으로는 선이나 면의 경계를 의미하며, 그래프에서는 정점 간의 연결을 나타냅니다.
그래프에서의 의미:
- Edge는 두 정점(Vertex) 간의 관계를 나타내는 선입니다.
- 예: 도로, 링크, 관계.

암기하기 쉬운 방법

1. Vertex

“V”로 시작하는 단어를 연결해 기억:
- Vertex → V → 점(Point): 꼭짓점처럼 그래프의 각 점을 나타낸다고 상상.
- “Vertex는 그래프의 데이터 점이다.”

2. Edge

“E”로 시작하는 단어를 연관:
- Edge → E → 선(Line): 정점(Vertex) 간의 선을 연결.
- “Edge는 그래프의 정점들을 잇는 선이다.”

연관 그림

Vertex: 점 ●
Edge: 선 ─
그래프: 여러 Vertex(점)들이 Edge(선)로 연결된 구조

“Vertex는 점이다. Edge는 점을 잇는 선이다.”

추가 예제

그래프:

Vertex: {A, B, C, D}
Edge: {(A, B), (B, C), (C, D)}

암기 활용

“A, B, C, D는 점(Vertex)이고, 점과 점을 연결하는 선이 Edge다.”
“Vertex는 ‘꼭짓점’, Edge는 ‘선’을 나타낸다.”

1. 그래프의 수학적 정의

그래프(Graph)는 ( G = (V, E) )로 표현됩니다:

( V ): 그래프의 정점(Vertex) 집합.
- 정점은 그래프에서 데이터의 단위로, 예를 들어 도시, 사람, 페이지 등이 될 수 있습니다.
- ( V ): 정점의 개수(그래프의 크기).
( E ): 그래프의 간선(Edge) 집합.
- 간선은 정점 간의 연결 관계를 나타냅니다.
- 간선은 다음 두 종류 중 하나로 나뉩니다:
  1. 무방향 그래프: 간선 ( (u, v) )는 양방향 연결을 의미.
  2. 방향 그래프: 간선 ( (u, v) )는 ( u \to v )로의 단방향 연결.

2. 그래프의 구성 요소

(1) 정점(Vertex):

그래프의 데이터 포인트.
예: ( V = {1, 2, 3, 4} ) (4개의 정점).

(2) 간선(Edge):

두 정점 간의 관계 또는 연결.
예: ( E = {(1, 2), (2, 3), (3, 4)} ) (3개의 간선).

(3) 그래프의 종류:

무방향 그래프(Undirected Graph):
- 간선이 양방향으로 연결.
- 예: ( (u, v) )와 ( (v, u) )가 동일.
방향 그래프(Directed Graph):
- 간선이 한 방향으로만 연결.
- 예: ( (u, v) )는 ( u \to v ), ( v \to u )는 별개의 간선.
가중치 그래프(Weighted Graph):
- 간선에 가중치(Weight)가 부여된 그래프.
- 예: ( (u, v, w) ), ( w )는 ( u \to v ) 간선의 가중치.

3. 그래프의 표현 방식

(1) 인접 리스트(Adjacency List):

정점별로 연결된 정점들을 리스트로 저장.
메모리 효율적 (( O(V + E) )).

예제:

V = {1, 2, 3, 4}
E = {(1, 2), (1, 3), (3, 4)}
Adjacency List:
1: [2, 3]
2: [1]
3: [1, 4]
4: [3]

(2) 인접 행렬(Adjacency Matrix):

정점 간 연결을 ( n \times n ) 행렬로 표현 (( n )은 정점의 개수).
메모리 소모가 많음 (( O(V^2) )).

예제:

V = {1, 2, 3, 4}
E = {(1, 2), (1, 3), (3, 4)}
Adjacency Matrix:
    1  2  3  4
1 [ 0, 1, 1, 0 ]
2 [ 1, 0, 0, 0 ]
3 [ 1, 0, 0, 1 ]
4 [ 0, 0, 1, 0 ]

4. BFS에서 그래프의 역할

BFS는 그래프에서 최단 경로 탐색 또는 연결된 컴포넌트 탐색을 위해 사용됩니다.

BFS는 정점 간의 연결(간선)을 따라 탐색하며, 시작점에서 가까운 정점부터 차례로 방문합니다.
각 정점의 인접 정점을 탐색할 때, 그래프의 구조(간선 정보)를 참조합니다.

5. 그래프의 실제 예시

실제 문제에 대응

소셜 네트워크 분석:
- 정점: 사용자
- 간선: 친구 관계
최단 경로 탐색:
- 정점: 도시
- 간선: 도시간 연결 도로
- 가중치: 도로 거리
웹 크롤링:
- 정점: 웹 페이지
- 간선: 페이지 간 하이퍼링크

6. BFS 예제 코드

from collections import deque

# 그래프 정의
graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}

# BFS 구현
def bfs(graph, start):
    visited = set()  # 방문 상태 저장
    queue = deque([start])  # 큐 초기화

    while queue:
        node = queue.popleft()  # 큐에서 노드 꺼냄
        if node not in visited:
            visited.add(node)  # 방문 상태에 추가
            print(f"Visited Node: {node}")
            queue.extend(graph[node])  # 인접 노드 큐에 추가

bfs(graph, 1)

출력 결과

Visited Node: 1
Visited Node: 2
Visited Node: 3
Visited Node: 4
Visited Node: 5

7. 정리

그래프의 수학적 정의:
- ( G = (V, E) ), 정점(Vertex)과 간선(Edge)로 구성된 자료구조.
BFS에서 그래프:
- 정점과 간선의 연결 정보를 기반으로 너비 우선 탐색 수행.
그래프 표현 방식:
- 인접 리스트(Adjacency List): 연결 정보만 저장.
- 인접 행렬(Adjacency Matrix): 정점 간의 모든 관계를 행렬로 표현.

Twitter Facebook LinkedIn

amiro