그래프 방식
1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현. 각 노드의 연결 형태를 기록
2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현. 연결된 노드를 튜플이나 리스트로 저장한다
이러한 그래프가 있다고 할 때,
인접 행렬 방식
# 인접행렬로 -> 길 수록 메모리 낭비
INF = int(1e9)
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)
인접 리스트 방식
# 인접 리스트 방식으로 -> 하나씩 확인해야 해서 정보를 얻는 속도가 느림
graph = [[] for _ in range(3)]
# (노드, 거리) 튜플을 append
graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))
print(graph)
노드 사이의 거리가 있는 경우
-> 양의 거리만 있을 때 다익스트라
-> 음의 거리도 있을 때 벨만 포드
DFS, BFS는 노드와 노드 사이의 거리가 동일하거나 1일 때 최적의 탐색이 가능 -> 인접 리스트가 편함
DFS(Depth First Search)
깊이 우선 탐색. 스택/재귀를 사용
현재 노드 스택에 삽입 후 방문 처리 -> 현재 노드와 연결 된 노드들 중 방문되지 않는 노드들을 스택에 삽입 후 방문
반복
1. 현재 노드 스택에 삽입하고 방문처리
2. 방문하지 않은 인접 노드를 스택에 넣고 방문 처리
3. 방문하지 않은 인접 노드 없으면 스택에서 노드를 꺼낸다
2,3 반복
스택 구현보다 재귀를 많이 쓴다
BFS(Breadth First Search)
너비 우선 탐색. 큐를 사용
현재 노드를 큐에 삽입 후 방문 처리 -> 현재 노드와 연결 된 노드들 중 방문되지 않는 노드들을 큐에 삽입 후 방문
반복
1. 현재 노드 큐에 삽입하고 방문 처리
2. 방문하지 않은 인접 노드 '모두'를 큐에 넣고 방문처리
3. 방문하지 않은 인접 노드 없으면 큐에서 노드를 꺼낸다.
2, 3 반복
큐 규현을 위해 collections 라이브러리의 deque를 쓴다
방문 처리를 하는 이유: 스택/큐에 삽입된 것이 다시 삽입되지 않도록
from collections import deque
def dfs(start_node, graph, d_visited):
# 방문 처리
d_visited[start_node] = True
print(start_node, end=' ')
# 인접 노드를 돌면서
for node in graph[start_node]:
# 방문하지 않았다면
if d_visited[node] == False:
# 재귀(스택에 넣는다)
dfs(node, graph, d_visited)
def bfs(start_node, graph, b_visited):
# 큐에 삽입
queue = deque([start_node])
# 방문 처리
b_visited[start_node] = True
# 빈 큐가 될 때까지
while queue:
# 큐에서 노드를 꺼낸다
v = queue.popleft()
print(v, end=' ')
# 인접 노드를 돌면서
for node in graph[v]:
# 방문하지 않았다면
if b_visited[node] == False:
# 큐에 넣는다
queue.append(node)
# 방문 처리
b_visited[node] = True
n, m, v = (map(int, input().split()))
graph = [ [] for _ in range(n+1)]
for _ in range(m):
node1, node2 = map(int, input().split())
graph[node1].append(node2)
graph[node2].append(node1)
for g in graph:
g.sort()
d_visited = [ False for _ in range(n+1)]
b_visited = [ False for _ in range(n+1)]
dfs(v, graph, d_visited)
print()
bfs(v, graph, b_visited)
+ DFS를 반복문으로 구현
1. 현재 노드를 스택에 삽입 (visited는 빈 리스트)
2. 스택에서 노드를 꺼낸다.
3. 꺼낸 노드가 방문되지 않았다면 인접 노드를 전부 스택에 넣는다
2, 3 반복
def dfs(start_node, graph):
st = [start_node]
visited = []
while st:
v = st.pop()
# 방문하지 않았다면
if v not in visited:
# 방문 처리
visited.append(v)
print(v, end=' ')
# 스택에 넣는다
st.extend(graph[v][::-1])
BFS는 가까운 노드부터 하나씩 탐색하기 때문에 최단 경로를 보장할 수 있다
DFS는 하나의 경로를 끝까지 탐색하기 때문에, 바뀔 수 있어 최단 경로를 보장하지 않는다.