DFS와 BFS
프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데
코딩 테스트에서는 이 두 방식 모두 필요하니 두 개념에 대해 바르게 알고 있어야 한다.
인접 행렬
방향 그래프
그래프의 연결 관계를 이차원배열
로 표현한다.
보통 adj[][]
형태로 많이 작성한다.
// adj[i][j]
: i에서 j로 가는 간선이 있다면 1, 없다면 0
인접 행렬 왜 사용?
-
[장점]
- 구현이 빠르다
- 노드가 서로 연결되어있는지 확인하기 쉽다.
//
adj[i][j] = 1
이면 노드 i와 노드 j는 연결되어 있다.
⇒ 시간복잡도 O(1) -
[단점]
- 전체 노드 개수: V 간선의 개수: E
- 특정 노드에 연결된 모든 노드를 검색할 때,
adj[i][1] ~ adj[i][V]
를 전부 확인해야한다.
시간복잡도 O(V)
⇒ 전체 노드 탐색 시 시간복잡도 O(V*V)
예제 with python
inf = 99999999999
graph =[
[0,7,5],
[7,0,INF],
[5,INF,0],
]
print(graph)
인접 리스트
인접 리스트 왜 사용?
-
[장점]
-
실제 연결된 노드만 저장한다
-
모든 vector의 원소의 개수 합 = 간선의 개수
⇒ 전체 노드 탐색 시 시간복잡도 O(E)2
-
-
[단점]
- 노드가 서로 연결되어있는지 확인하는데 오래 걸린다.
인접 행렬
은 adj[i][j]의 값이 1인지 확인하면 연결된 것을 알지만인접 리스트
의 경우는 adj[i]가 j를 원소로 갖는지 확인해봐야한다.
⇒ 시간복잡도 O(V)
예제 with python
graph = [[] for _ in range(3)]
#노드 0에 연결된 노드 정보 저장(노드,거리)
graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))
print(graph)
이것이 취업을 위한 코딩 테스트다 with 파이썬
DFS
- 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
- 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴
- 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하여 순회
- 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용
def dfs(graph, v, visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
else:
print(i)
visited = [False] * 9
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
dfs(graph, 1, visited)
BFS
from collections import deque
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
graph =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited= [False] * 9
bfs(graph,1, visited)
Author And Source
이 문제에 관하여(DFS와 BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@eunseo2/DFS와-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)