[자료구조] 10. 그래프, BFS, DFS, 위상 정렬

1. 그래프

 

- 그래프란?

- 그래프 관련 용어

- 방향그래프

- 무방향 그래프

- 그래프의 구현 (인접행렬/  인접 리스트 )

 

 

- 방향그래프 (Directed Graph)

두 정점을 잇는 간선에 방향이 있는 그래프

 

 

- 무방향 그래프 (Undirected Graph)

두 정점을 잇는 간선에 방향이 없는 그래프

 

 

 

- 그래프의 구현 (인접행렬; Adjacency Matrix)

원소 = 1 : 0 ? 이어져있다 : 이어지지 않았다.

 

원소가 1이면 두 정점은 이어져있다.

원소가 0이면 두 정점은 이어지지 않았다.

 

출처 : https://suyeon96.tistory.com/32

 

 

# 무방향 그래프

대각선을 기준으로 대칭을 이룸

따라서... 간선 수 x 2 = 1의 개수

 

# 방향 그래프

대칭을 이루지 않기 때문에(방향이 있으니... 당연히 대칭이 아님)

간선 수 = 1의 개수

 

# 무방향 그래프

아래와 같이 코드로 나타낼 수 있는데 이렇게  인접 행렬로 그래프를 나타낼 경우, 

정점이 많아질 수록 인접행렬의 크기가 커진다는 단점을 가짐 

e.g., 간선 수는 2000개라고 가정하면, 20000^2 크기의 인접 행렬이 필요함

G = [[0, 1, 1, 1], 
     [1, 0, 1, 1], 
     [1, 1, 0, 1],
     [0, 1, 1, 0]]

G[0][2]

// 1 출력

 

- 그래프의 구현 (인접리스트; Adjacency List)

인접하는 정점들을 나열한다.

dictionary로 표현 가능

[key] = 정점
[value] = 연결된 정점들 (인접 정점)

 

 

 

 

 

2. 너비우선탐색(BFS)과 깊이우선탐색(DFS)

 

 

 

 

 

2.1 너비 우선 탐색 (BFS; Breadth-First Search)

 

⁘ 인접한 노드를 우선 방문

⁘  level - order (레벨 순회) 

⁘ Queue를 이용하여 구현 - FIFO(선입선출)

 

[최전방 출력 - 최전방 자식 enqueue - 최전방 dequeue]

 

 

- 너비 우선 탐색 과정

 

인접 정점 중 낮은 숫자가 우선순위임을 가정

4 출력

4와 인접한 2, 3

 

 

 

 

 

 

 

2.2 깊이 우선 탐색 (DFS; Depth-First Search)

 

⁘ 갈 수 있는 가장 깊은 곳까지 우선 탐색 

⁘ Pre-order / In-order / Post-order 순회 (전위, 중위, 후위)

⁘ 재귀를 이용하여 구현 

 

[전위 순회] 루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

[중위 순회] 왼쪽 서브트리 -> 루트 노드 -> 오른쪽 서브트리

[후위 순회] 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 노드

 

 

 

 

 

 

 

 

2.3 너비우선탐색과 깊이우선탐색의 문제점

연결그래프가 아니면 모든 정점의 방문을 보장하지 않는다.

그래도.... 정점 A에서 정점 Y로 가는 보행(walk)이 존재하는 지 여부 판단 가능함

 

 

 

 

 

 

 

 

3. 위상 정렬 (Topological Sort)

 

- 위상정렬이란?

- 위상정렬을 위한 순서 찾기 (진입차수)

 

 

- 위상정렬이란?

순서에 어긋나지 않도록 주어진 방향 그래프의 모든 정점을 한 번씩 방문하는 방법

 

! 모든 방향 그래프의 위상 순서가 반드시 유일하지는 않음

 

 

 

- 위상정렬을 위한 순서 찾기 (진입차수)

진입 차수 = 들어오는 정점의 수

진입차수가 0인 정점(key)과 연결된 모서리(value)를 모두 제거한다.

(제거 대상 노드가 여럿일 경우, 그 중 하나만 제거)

 

1) 진입 차수 구하기

나(정점)를 가리키는 간선이 몇 개인가?

2) 진입차수 0인 정점과 연결된 간선 삭제

3) 진입차수 업데이트

 

 

 

 

 

 

 

 

 

 

 

 

참고

파이썬과 함께하는 자료구조의 이해 - 예스24