🔍 그래프 탐색이란?
- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
- ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지
📍BFS(Breadth-First Search, 너비 우선 탐색)
그래프의 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택
- 너비 우선 탐색이 깊이 우선 탐색보다 좀 더 복잡하다.
- 일반적으로 DFS보다 수행 시간이 더 효율적이다.
✨ BFS의 특징
- BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색하기 때문에 직관적이지 않은 면이 있다.
- BFS 알고리즘의 가장 큰 특징은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
- 즉, 선입선출(FIFO) 원칙으로 탐색
- 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
- BFS는 재귀적으로 동작하지 않는다.
🔴 구현 시 주의할 점
- 파이썬에서 큐를 list 타입을 사용해서 자료를 입력할 때는 list.append(something), 출력할 때는 list.pop(0)와 같이 구현하는 경우는 시간복잡도가 O(N)이라 시간적으로 매우 비효율적인 코드가 만들어지게 된다.
- 라이브러리 collections의 deque를 사용하면 시간을 절약할 수 있게 된다.
🔢 BFS 구현 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드의 방문하지 않은 모든 인접 노드를 모두 큐에 삽입하고 방문 처리
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복
💻 BFS 구현
- BFS 알고리즘을 구현하는 방법은 2가지가 있다.
- 인접행렬, queue 자료구조
- 인접리스트, queue 자료구조
1️⃣ 인접행렬과 큐(Queue) 자료구조를 사용한 BFS 구현
- 시작 노드를 큐에 추가하고 방문 표시
- 큐에서 노드를 꺼내고 해당 노드를 방문
- 현재 노드와 연결된 인접한 노드 중에서 방문하지 않은 노드가 있다면 큐에 추가하고 방문 표시
- 해당 과정을 큐가 비어있을 때까지 반복
from collections import deque
def bfs(adj_matrix, start_node):
num_nodes = len(adj_matrix)
visited = [False] * num_nodes # 방문한 노드를 표시하기 위한 배열
queue = deque() # 큐 생성
queue.append(start_node) # 시작 노드를 큐에 추가
visited[start_node] = True # 시작 노드를 방문 표시
while queue:
current_node = queue.popleft() # 큐에서 노드를 꺼내옴
print(current_node) # 노드 방문 순서를 출력하거나 다른 작업 수행
for next_node in range(num_nodes):
# 현재 노드와 연결된 인접한 노드를 찾음
if adj_matrix[current_node][next_node] == 1 and not visited[next_node]:
queue.append(next_node) # 큐에 추가
visited[next_node] = True # 방문 표시- adj_matrix : 인접한 노드간의 연결 정보를 나타내는 2차원 배열
- bfs : 시작 노드 start_node를 입력으로 받아 BFS 수행
- visited : 방문한 노드를 표시하기 위한 배열
- queue : 노드를 저장하기 위한 큐
2️⃣ 인접리스트와 큐(Queue) 자료구조를 사용한 BFS 구현
- 시작 노드를 큐에 추가하고 방문 표시
- 큐에서 노드를 꺼내고 해당 노드를 방문
- 현재 노드와 연결된 인접한 노드 중 방문하지 않은 노드가 있다면 큐에 추가하고 방문 표시
- 큐가 비어있을 때까지 다음 과정을 반복
from collections import deque
def bfs(adj_list, start_node):
num_nodes = len(adj_list)
visted = [False] * num_nodes # 방문한 노드를 표시하기 위한 배열
queue = deque() # 큐 생성
queue.append(start_node) # 시작 노드를 큐에 추가
visted[start_node] = True # 시작 노드를 방문 표시
while queue:
current_node = queue.popleft() # 큐에서 노드를 꺼내옴
print(current_node) # 노드 방문 순서를 출력하거나 다른 작업 수행
for next_node in adj_list[current_node]:
if not visited[next_node]:
queue.append(next_node) # 큐에 추가
visited[next_node] = True # 방문 추가- adj_list : 각 노드의 인접한 노드들을 리스트로 표현한 2차원 배열
- bfs : 인접리스트 adj_list와 시작 노드 start_node를 입력으로 받아 BFS 수행
- visited : 방문한 노드를 표시하기 위한 노드
- queue : 노드를 저장하기 위한 큐
📍DFS(Depth-First Search, 깊이 우선 탐색)
루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기(branch)를 완벽하게 탐색하는 방법
- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
- 사용하는 경우 : 모든 노드를 방문하고자 하는 경우에 이 방법을 선택
- 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색에 비해서 느리다.
✨ DFS의 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
- 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
- DFS는 먼저 방문한 노드에 연결된 노드보다 현재 방문한 노드에 연결된 노드를 방문해야 한 방향으로 갈 수 있는 스택(Stack)을 사용한다.
- DFS의 가장 큰 특징은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
- DFS 알고리즘은 재귀적인 특징이 있다.
- 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
🔢 DFS 구현 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다.
- 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
💻 DFS 구현
- DFS를 구현하는 방법은 4가지 방법이 있다.
- 인접행렬과 stack 자료구조를 이용한 방법
- 인접행렬과 재귀함수를 이용한 방법
- 인접리스트와 stack 자료구조를 이용한 방법
- 인접리스트와 재귀함수를 이용한 방법
1️⃣ 인접행렬과 스택(stack) 자료구조를 이용한 DFS 구현
- 스택에서 노드를 꺼내고 해당 노드를 방문
- 현재 노드와 연결된 인접한 노드 중 방문하지 않은 노드가 있다면 스택에 추가하고 방문 표시
- 각 노드를 방문할 때마다 print(current_node)을 통해 노드 방문 순서를 출력
- 스택이 비어있을 때까지 해당 과정을 반복
def dfs(adj_matrix, start_node):
num_nodes = len(adj_matrix)
visited = [False] * num_nodes # 방문한 노드를 표시하기 위한 배열
stack = []
stack.append(start_node) # 시작 노드를 스택에 추가
visited[start_node] = True # 시작 노드를 방문 표시
while stack:
current_node = stack.pop() # 스택에서 노드를 꺼냄
print(current_node) # 노드 방문 순서를 출력하거나 다른 작업을 수행
for next_node in range(num_nodes):
# 현재 노드와 연결된 인접한 노드를 찾음
if adj_matrix[current_node][next_node] == 1 and not visited[next_node]:
stack.append(next_node) # 스택에 추가
visited[next_node] = True # 방문 표시- adj_matrix : 인접한 노드간의 연결 정보를 나타내는 2차원 배열
- adj_matrix의 인덱스 i, j의 값이 1이면 노드 i와 j가 연결되어 있음을 의미
- dfs : 시작 노드 start_node를 입력으로 받아 DFS를 수행
- visited : 방문한 노드를 표시하기 위한 배열
- stack : 노드를 저장하기 위한 스택
- 시작 노드를 스택에 추가하고 방문 표시
2️⃣ 인접행렬과 재귀함수를 이용한 DFS 구현
- 현재 노드를 방문 표시하고 노드 방문 순서를 출력하거나 다른 작업을 수행
- 현재 노드와 연결된 인접한 노드 중 방문하지 않은 노드가 있다면 해당 노드를 시작 노드로 재귀 함수를 호출
- 이를 통해서 깊이 우선 탐색을 수행
- 각 노드를 시작 노드로 하여 DFS를 수행, 시작 노드로 방문하지 않은 노드를 선택하여 DFS를 호출
def dfs(adj_matrix, current_node, visited):
visited[current_node] = True # 현재 노드를 방문 표시
print(current_node) # 노드 방문 순서를 출력하거나 다른 작업을 수행
for next_node in range(len(adj_matrix[current_node])):
# 현재 노드와 연결된 인접한 노드를 찾음
if adj_matrix[current_node][next_node] == 1 and not visited[next_node]:
# 재귀 호출
dfs(adj_matrix, next_node, visited)
# 인접행렬
adj_matrix = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 1],
[1, 0, 0, 0, 1],
[0, 1, 0, 0, 0],
[0, 1, 1, 0, 0]
]
num_nodes = len(adj_matrix)
# 방문한 노드를 표시하기 위한 배열
visited = [False] * (num_nodes)
# 각 노드를 시작 노드로 하여 DFS 수행
for start_node in range(num_nodes):
if not visited[start_node]:
dfs(adj_matrix, start_node, visited)- adj_matrix: 인접한 노드간의 연결 정보를 나타내는 2차원 배열
- dfs : 현재 노드 current_node와 방문한 노드를 표시하는 visited 배열을 입력으로 받아 DFS 수행
- visited : 방문한 노드를 표시하는 배열
3️⃣ 인접리스트와 스택(stack) 자료구조를 이용한 DFS 구현
- 시작 노드를 스택에 추가
- 스택에서 노드를 꺼내고, 해당 노드를 방문하지 않았다면 방문 표시를 하고 노드 방문 순서를 출력하거나 다른 작업을 수행
- 현재 노드와 연결된 인접한 노드 중 방문하지 않은 노드가 있다면 해당 노드를 스택에 추가
- 시작 노드로 방문하지 않은 노드를 선택하여 DFS 호출
- 해당 과정을 스택이 비어있을 때까지 반복
def dfs(adj_list, stack_node):
num_nodes = len(adj_list)
visited = [False] * num_nodes # 방문한 노드를 표시하기 위한 배열
stack = [] # 스택 생성
stack.append(start_node) # 시작 노드를 스택에 추가
while stack:
current_node = stack.pop() # 스택에서 노드를 꺼내옴
if not visited[current_node]:
visited[current_node] = True # 방문 표시
print(current_node) # 노드 방문 순서를 출력하거나 다른 작업을 수행
for next_node in adj_list[current_node]:
if not visited[next_node]:
stack.append(next_node) # 스택에 추가
# 인접리스트
adj_list = [
[1, 2],
[0, 3, 4],
[0, 4],
[1],
[1, 2]
]
num_nodes = len(adj_list)
# 각 노드를 시작 노드로 하여 DFS 수행
for start_node in range(num_nodes):
dfs(adj_list, start_node)- adj_list : 각 노드의 인접한 노드들을 리스트로 표현한 2차원 배열
- dfs : 인접리스트 adj_list와 시작 노드 start_node를 입력으로 받아 DFS 수행하는 함수
- visited : 방문한 노드를 표시하기 위한 배열
- stack : 배열과 노드를 저장하기 위한 스택
4️⃣ 인접리스트와 재귀함수를 이용한 DFS 구현
- 현재 노드를 방문 표시하고 노드 방문 순서를 출력하거나 다른 작업을 수행
- 현재 노드와 연결된 인접한 노드 중 방문하지 않은 노드가 있다면 해당 노드를 시작 노드로 재귀 호출을 진행
- 이를 통해 깊이 우선 탐색 진행
- 시작 노드로 방문하지 않은 노드를 선택하여 DFS 호출
def dfs(adj_list, current_node, visited):
visited[current_node] = True # 현재 노드를 방문 표시
print(current_node) # 노드 방문 순서를 출력하거나 다른 작업을 수행
for next_node in adj_list[current_node]:
if not visited[next_node]:
dfs(adj_list, next_node, visited) # 재귀 호출
# 인접리스트
adj_list = [
[1, 2],
[0, 3, 4],
[0, 4],
[1],
[1, 2]
]
num_nodes = len(adj_list)
visited = [False] * num_nodes # 방문한 노드를 표시하기 위한 배열
# 각 노드를 시작 노드로 하여 DFS 수행
for start_node in range(num_nodes):
if not visited[start_node]:
dfs(adj_list, start_node, visited)- adj_list : 각 노드의 인접한 노드들을 리스트로 표현한 2차원 배열
- dfs : 인접리스트 adj_list와 현재 노드 current_node, 방문한 노드를 표시하는 visited 배열을 입력받아 DFS 수행
- visited : 방문한 노드를 표시하는 배열
Reference
https://namu.wiki/w/%EA%B9%8A%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89
https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89
Welcome! This is cocoball world!