너비우선탐색 BFS와 깊이우선탐색 DFS

너비우선탐색(BFS)

너비우선탐색(BFS)은 시작 노드에서 너비를 우선으로 탐색한다. 깊게보다는 넓게 탐색하는 방법이다. 너비우선탐색은 주로 queue 자료구조를 이용해서 구현한다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모드 큐에 삽입하고 방문 처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

from collections import deque

def BFS(graph, start, visited):
    #큐 구현을 위해 deque 라이브러리 사용
    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

graph = [
    [ ],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
#각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False]*9
BFS(graph, 1, visited)

 

깊이우선 탐색(DFS)

깊이우선탐색은 넓게보다는 깊게 탐색하는 방법이다. 주로 스택 자료구조를 사용하거나 재귀함수를 이용한다.

1. 탐색 시작 노드를 스택에 삽입하고 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

def dfs(graph, v, visited):
	#현재 노드를 방문처리
	visited[v] = True
	print(v)
	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]
]

visited = [false] * 9
dfs(graph, 1, visited)]