[알고리즘] DFS & BFS

대표적인 그래프 탐색 알고리즘 DFS & BFS

 

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 

스택: 파이썬에서 리스트를 이용하기

큐: 파이썬의 리스트로도 구현가능하지만, 시간복잡도 문제(원하는 인덱스 추출후 다른 인덱스들을 조정해주는 과정이 필요하기 떄문에 낭비가 심함)가 있으므로 덱을 이용하여 구현!

from collections import deque

queue=deque()

queue.append(7)

queue.popleft() 

 

재귀함수 : 자기 자신을 다시 호출하는 함수

ex) 유클리드 호제법 (최대공약수 계산)

- 두 자연수 A,B에 대해 (A>B) A를 B로 나눈 나머지를 R이라고 하면

A,B의 최대공약수는 B,R의 최대공약수와 같다

 

def gcd(a,b):

if a%b==0:

return b

else:

return gcd(b,a%b)

 

DFS (깊이 우선 탐색) : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

스택 자료구조( 혹은 재귀함수)를 이용하여 구현한다

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

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 반문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

3. 더이상 과정을 수행할수 없을 때까지 반복

 

*파이썬에서는 그래프를 표현하기 위해 이차원 리스트로 나타낸다

 

visited=[False]*9

dfs(graph,1,visited)

def dfs(graph,v,visited):
	visited[v]=True
    print(v,end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph,i,visited)

 

 

BFS ( 너비 우선 탐색) : 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

큐 자료구조를 이용한다

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

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

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

from collections import deque

visited=[False]*9
bfs(graph,1,visited)

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