Depth-First Search

그래프 탐색

그래프 Graph는 노드 Node와 간선 Edge로 표현됨

그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것

두 노드가 간선으로 연결되어 있으면 두 노드는 인접하다(adjacent)라고 표현

 

 

* 인접 행렬 Adjacency Matrix : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

* 인접 리스트 Adjacency List : 리스트로 그래프의 연결 관계를 표현하는 방식

 

인접 행렬 Adjacency Matrix

2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

그래프를 인접 행렬로 표현 시 파이썬에서는 2차원 리스트로 구현 가능

연결되어있지 않은 노드끼리는 infinity의 비용으로 작성

-> 실제 코드에서는 987654321과 같은 값으로 초기화함

	0	1	2
0	0	7	5
1	7	0	INF
2	5	INF	0

INF = 987654321

# 2차원 리스트로 인접 행렬
graph =[
[0,7,5],
[7,9,INF],
[5,INF,0]
]

 

인접 리스트 Adjacency List

모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장

파이썬에서는 2차원 리스트를 이용하면 됨

인접 리스트에서는 인접 행렬보다 메모리는 효율적으로 사용하지만 정보를 얻는 속도가 느림

# 행이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0,7))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0,5))

 

[[(1,7), (2,5)], [(0,7)],[(0,5)]]

 

Depth-First Search ; DFS

깊이 우선 탐색 알고리즘

; 특정 경로로 탐색하다가 특정 상황에서 깊숙이 들어가서 노드 방문 후 다시 돌아가 다른 경로를 탐색함

스택 자료구조에 기초함

실제로는 스택 쓰지 않아도 되고 탐색 수행에 데이터 개수가 N개인 경우 O(N) 시간이 소요됨

구현은 재귀 함수를 이용했을 때 간결하게 구현 가능

 

1) 탐색 시작 노드를 스택에 삽입하고 방문 처리

2) 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면 인접 노드를 스택에 넣고 방문 처리

-> 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼냄

3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

def dfs(graph, v, visited):
	visited[v] = True
    
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
         
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False] * 9

dfs(graph, 1, visited)

 

Breadth First Search ; BFS

너비 우선 탐색

가까운 노드부터 탐색하는 알고리즘

선입선출 방식인 큐 자료구조를 이용하여 주로 구현

탐색 수행에 데이터 개수가 N개인 경우 O(N) 시간이 소요됨

일반적인 경우 실제 수행 시간은 DFS보다 좋은 편

 

동작 방식

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리

2) 큐에서 노드 꺼내서 해당 노드 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

3) 2의 과정을 계속 반복

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v=queue.popleft()
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] =True

 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

2차원 배열에서 탐색 문제 만날 시 그래프 형태로 바꿔서 생각하는 연습 하기