그래프 탐색 알고리즘
- 그래프의 가장 기본적인 연산
-
시작 정점부터 차례대로 모든 정점들을 한 번씩 방문
-
많은 문제들이 단순히 탐색만으로 해결됨
- 도로망 : 특정 도시에서 다른 도시로 갈 수 있는 지 여부
- 전자회로 : 특정 단자와 다른 단자의 연결 여부대표적인 알고리즘
-
BFS( 너비 우선 탐색)
-
DFS( 깊이 우선 탐색)
💡너무나 중요하다!!!! ( 그냥 외우듯이 술 술 나와야함)
-
BFS
시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
-
시간 복잡도 :
- O( |V| + |E| ) 을 갖는다
- |V| : 노드의 갯수
- |E| : 엣지의 갯수
-
큐를 사용하여 구현됨
-
적용
- 두 노드의 가장 가까운 루트 찾기
- Ford - Fulkerson algorithms (Maximum Flow in net works)
간단한 그림 예시
- 인접 노드의 순서는 어떻게 넣든지 상관 없다. 예를 들어 1번 그림을 보면 1의 인접 노드를 1,2,3 순으로 큐에넣던지 3,2,1 순으로 넣던지 동일한 결과를 얻는다.
- 큐에 인접한 노드를 넣을 때 visited에 해당 노드를 기록하는 것이 좋다.
코드 구현
- BFS 문제를 풀기 위해서는 우리가 이전에 배운 그래프 표현을 사용하여 인접 리스트나 인접 배열을 사용하여 구현이 되었다고 가정한다.
from collections import deque
# graph가 인접 리스트 일 때
def bfs(graph,startNode):
visited = []
q = deque() # deque 선언
q.append(startNode)
#que가 empty가 될 때 까지 반복
while q:
#큐에서 꺼냄
cur_node = q.popleft()
#인접 노드 추가
# 큐에 집어 넣을 때 중복 검사한다 !
for i in graph[cur_node]:
if i not in visited:
visited.append(i)
q.append(i)
return visited
스택,큐에 집어 넣을 때 검사를 하면 중복을 피할 수 있다.
이때 말하는 중복은 s에서 뺄 때 visited에 검사를 한다면 이미 방문했던 node도 s에 다시 들어가기 때문이다. (이는 불필요한 중복)
BFS shortestPath
이해를 돕기 위한 예시 코드
from collections import deque
def shortest_path(predecessor_node,start_node,end_node):
path = [end_node]
cur_node = end_node
#start node가 될 때 까지 찾는다.
while cur_node != start_node:
cur_node = predecessor_node[cur_node]
path.append(cur_node)
#역순으로 경로 저장
path.reverse()
return path
def bfs_shortest_node(graph,start_node,end_node):
visited = []
q = deque()
predecessor_node = {} # 부모 노드 저장
while q:
current_node = q.popleft()
visited.append(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
q.append(neighbor)
predecessor_node[neighbor] = current_node
print(shortest_path(predecessor_node,start_node,end_node))
DFS
깊이 우선 탐색
- DFS : Depth - First - Search
- 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 되돌아와서 (back tracking)그곳으로 부터 다른 방향으로 다시 탐색 진행
- 되돌아가기 위해서는 스택이 필요
- 순환함수 호출로 묵시적인 스택 이용
묵시적 스택
-
스택을 명시적으로 이용하지 않고 재귀 함수 호출을 이용하여 DFS를 구현하는 것을 의미한다.
-
재귀 함수를 이용하면서 시스템의 콜 스택이 사용되는데 이를 이용하여 시스템 스택에 해당 함수가 쌓이고 함수가 스택에서 호출 정보가 제거된다.
-
즉, 스택을 이용하여 구현이 가능하고, 스택을 이용하지 않고 재귀함수를 이용하여 구현이 가능하다는 의미다.
간단한 그림으로 보기
BFS의 예시 그래프와 동일한 그래프를 DFS로 탐색 했을 경우 얻는 과정이다. 같은 그래프이지만 다른 탐색 결과를 얻게 된다.
💡 마찬가지로 인접한 노드의 순서는 어떻게 들어가던지 상관없다.
코드 구현
- stack을 사용한 구현
# graph가 인접 리스트일 때
def dfs(graph, start_node):
visited = [] # 방문한 노드를 저장할 리스트
s = [start_node] # 방문할 노드를 저장할 스택
while s:
current_node = s.pop() # 스택에서 노드를 꺼냄
if current_node not in visited: # 현재 노드가 방문한 적이 없다면
visited.append(current_node) # 방문 목록에 추가
# 인접 노드들을 스택에 추가 (방문한 노드는 제외)
for i in graph[current_node]:
if i not in visited:
s.append(i)
return visited
💡 '왜 DFS는 중복 입력 방지를 위해 s에 넣을 때 방문 처리를 하지 않나요?' 라는 의문이 생길 수 있다. 하지만 DFS는 BFS와 달리 Stack의 특성을 이용해야 하기 때문에 s에 넣을 때 방문 처리를 하면 DFS의 방문 순서대로 출력이 되지 않는다!
- 재귀를 사용한 구현
#DFS 묵시적 스택
visited = []
def dfs(graph,start_node,visited = None):
if visited is None:
visited = []
if start_node not in visited:
visited.append(start_node)
neighbors = graph[start_node]
for neighbor in neighbors:
dfs(graph,neighbor,visited)
return visited
