Graph(2)-BFS/DFS

저번시간에는 그래프의 정의와 종류 그리고 구현하는 방식에 대해서 알아보았습니다. 그렇다면 이번 시간에는 그래프를 순회하는 방식에 대해서 알아보도록 하겠습니다. *자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조이다. *탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.

그래프 순회

그래프를 순회 한다는 것은 모든 노드를 지나야 한다는 것입니다. 대표적인 방식이 DFS와 BFS 입니다. 

BFS(Breadth Frist Search) 

BFS는 너비 우선 탐색이라는 의미이고 쉽게 말하면 가까운 노드부터 우선적으로 탐색하는 알고리즘 입니다. 그래프 순회를 할 때, 시작점이 주어질텐데, 이를 루트 노드라 생각하여, level 별로 탐색을 하는 것이 BFS입니다. 이때, BFS를 구현하는 방식은 선입선출 방식인 queue 자료구조를 이용하는 것이 정석입니다. 실제로 구현함에 있어서 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다.

• queue 자료구조 이용 -> deque 라이브러리 사용
• O(N)의 시간 소요
• 일반적인 경우 실제 수행시간은 BFS가 DFS보다 좋은 편

from collections import deque

#노드가 8개라고 정의 했을 때,
#방문정보 확인을 위한 1차원 리스트, 인덱스 번호와 노드 번호를 일치하기 위해 [False] * 9
visited = [False] * (9)

#bfs 함수 정의
def bfs(graph, start):
	#큐 구현을 위해 deque 라이브러리 활용
    q = deque()
    #현재 노드 방문처리
    visited[start] = True
    
    #큐가 빌 때까지 반복
    while q:
    	now = q.popleft() #큐에서 하나의 원소를 뽑아 출력
        print(now, end='') # 큐에서 꺼낸 순서 = 큐에 들어간 순서 즉 방문 순서
        for v in graph[now]: #현재 노드와 연결된 모든 노드에 대하여
        	if not visited[v]:
            	q.append(v)
                visited[v] = True
                
 # 각 노드에 대한 연결 정보를 2차원 리스트 즉, 인접 리스트 형식으로 표현
 graph = [
 	[], # 빈 리스트 1번노드부터 시작하기 때문에
    [2,3,8], # 1번 노드와 연결된 노드들의 집합
    [1,7], # 2번 노드와 연결된 노드들의 집합
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
 ]
 
 bfs(graph, 1) #그래프 정보와 시작 노드를 매개변수로 입력
 
 #결과
 1 2 3 8 7 4 5 6 # 순회 순서

DFS(Depth First Search)

DFS는 깊이 우선 탐색이라는 의미이며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색의 경우 스택 자료구조에 기초한다는 점에서 구현이 간단하다. DFS는 출발점에 시작해서, 막다른 지점에 도착할 때까지 깊게 이동합니다. 만약 가다가 막히면 다시 그 전 노드로 돌아가고, 또 길이 있으면 깊게 이동하는 식의 과정을 통해 그래프를 순회할 수 있습니다.

• 스택 자료구조에 기반 -> 실제 구현은 재귀 함수를 이용, 재귀함수는 내부적으로 스택 자료구조와 유사
• 데이터의 개수가 N개일 경우 O(N)의 시간이 소요된다
• BFS 보다 실제 수행시간이 느리다.

#방문정보 처리를 위한 1차원 리스트 만들기
visited = [False] * 9

#dfs함수 정의
def dfs(graph, start):
	#현재 노드 방문처리
    visited[start] = True
    print(start, end='')
    #현재 노드와 연결된 모든 노드를 재귀적으로 방문한다.
    for v in graph[start]:
    	if not visited[v]:
        	dfs(graph, v)
            
# 각 노드에 대한 연결 정보를 2차원 리스트 즉, 인접 리스트 형식으로 표현
 graph = [
 	[], # 빈 리스트 1번노드부터 시작하기 때문에, 컴퓨터는 0부터 시작.
    [2,3,8], # 1번 노드와 연결된 노드들의 집합
    [1,7], # 2번 노드와 연결된 노드들의 집합
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
 ]
 
 dfs(graph, 1) #그래프 정보와 시작 노드를 매개변수로 입력
 
 #결과
1 2 7 6 8 3 4 5# 순회 순서