그래프 알고리즘
그래프를 표현하고 이해하는 알고리즘
→ 그래프 : 정점(Vertex) 과 간선(Edge)으로 구성된 자료구조
그래프 구조 예시
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
}
[분류]
- 탐색 알고리즘 : 각각의 정점들이 연결된 상태 (DFS, BFS)
- DFS( Depth First Search )
- BFS( Breadth First Search )
- 그래프의 형태 : 인접 행렬 or 이차원 배열 형태
- 최단 경로 알고리즘 : 두 정점의 최단 경로 (다익스트라 알고리즘 , 벨만 포드 알고리즘, 플로이드 와샬 알고리즘)
- 최소 신장 트리 : 모든 정점을 연결하는 최단 경로. 모든 경로를 지나는 최소값 ( 쿠르스칼 알고리즘, 프림 알고리즘)
DFS (Depth First Search)
DFS는 그래프의 깊이를 우선으로 탐색하는 알고리즘
즉, 한 정점에서 출발하여 가능한 깊이까지 들어가고, 더 이상 갈 곳이 없으면 다시 되돌아오는 방식입니다
DFS는 스택 자료구조를 사용하거나 재귀 호출을 통해 구현
DFS 알고리즘 동작 과정
- 시작 정점을 스택(또는 재귀 호출)에 추가하고 방문 처리
- 스택의 최상단 정점을 가져와 인접한 정점 중 방문하지 않은 정점을 스택에 추가하고 방문 처리
- 더 이상 방문할 정점이 없으면 스택에서 정점을 꺼내고, 다시 스택의 최상단 정점에 대해 2번 과정을 반복
- 스택이 빈 상태가 되면 탐색을 종료
구현 : 재귀
def dfs_recursive(graph, v, visited):
visited[v] = True
print(v, end=' ') # 방문한 정점 출력
for neighbor in graph[v]:
if not visited[neighbor]:
dfs_recursive(graph, neighbor, visited)
# 그래프를 인접 리스트로 표현
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1],
5: [2]
}
# 방문 정보를 저장하는 리스트
visited = [False] * len(graph)
# 0번 정점부터 DFS 시작
dfs_recursive(graph, 0, visited)
구현 : 스택
def dfs_stack(graph, start):
visited = [False] * len(graph)
stack = [start]
while stack:
v = stack.pop()
if not visited[v]:
print(v, end=' ') # 방문한 정점 출력
visited[v] = True
stack.extend(reversed(graph[v])) # 인접 정점 추가 (순서를 유지하기 위해 역순으로 추가)
# 0번 정점부터 DFS 시작
dfs_stack(graph, 0)
BFS (Breadth First Search)
BFS는 그래프의 너비를 우선으로 탐색하는 알고리즘
즉, 한 정점에서 출발하여 인접한 모든 정점을 우선 방문하고, 그 다음 깊이로 이동하는 방식
BFS는 큐 자료구조를 사용하여 구현
BFS 알고리즘 동작 과정
- 시작 정점을 큐에 추가하고 방문 처리
- 큐의 앞에서 정점을 꺼내 해당 정점에 인접한 모든 정점 중 방문하지 않은 정점을 큐에 추가하고 방문 처리
- 큐가 빈 상태가 되면 탐색을 종료
구현
from collections import deque
def bfs(graph, start):
visited = [False] * len(graph)
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ') # 방문한 정점 출력
for neighbor in graph[v]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
# 0번 정점부터 BFS 시작
bfs(graph, 0)
요약
- DFS (Depth-First Search):
- 깊이를 우선으로 탐색
- 스택 또는 재귀 호출 사용
- 구현이 간단하고, 그래프의 모든 경로를 탐색할 때 유용
- BFS (Breadth-First Search):
- 너비를 우선으로 탐색
- 큐 사용
- 최단 경로를 찾는 데 유용
인접 행렬의 DFS, BFS
인접 행렬은 지도를 그래프 형태로 바꿔놓은 것이라 생각하면 쉬움
'''
6 6
0 1 1 1 1 1
0 1 0 0 0 1
0 1 0 1 0 1
0 1 0 1 0 0
0 0 0 1 1 0
1 1 1 1 1 0
'''
N, M = map(int, input().split())
arr = []
for _ in range(N):
row = list(map(int, input().split()))
arr.append(row)
print(arr)
[0, 1, 1, 1, 1, 1]
[0, 1, 0, 0, 0, 1]
[0, 1, 0, 1, 0, 1]
[0, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0]
[1, 1, 1, 1, 1, 0]
- 6x6 배열이며 (0,0) 에서 (5,5)의 위치로 이동하기
# DFS
visited = [[False] * M for _ in range(N)]
dy = (-1, 1, 0, 0)
dx = (0, 0, -1, 1)
def dfs(y, x):
print(y, x)
visited[y][x] = True
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if not(0 <= ny < N and 0 <= nx < M):
continue
if arr[ny][nx] == 1:
continue
if not visited[ny][nx]:
dfs(ny, nx)
dfs(0, 0)
# BFS
from collections import deque
def bfs(y, x):
visited = [[False] * M for _ in range(N)]
dy = (-1, 1, 0, 0)
dx = (0, 0, -1, 1)
visited[y][x] = True
que = deque()
que.append((y, x))
while que:
y, x = que.popleft()
print(y, x)
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if not(0 <= ny < N and 0 <= nx < M):
continue
if arr[ny][nx] == 1:
continue
if not visited[ny][nx]:
visited[ny][nx] = True
que.append((ny, nx))
bfs(0, 0)
- BFS는 방문 가능다하고 무조건 방문하는 것이 아니라, 방문 가능한 곳을 큐에 넣어두고 순서대로 방문
인접리스트의 DFS, BFS
- 노드(node), 엣지(edge) 개념 활용
- 인접 리스트의 그래프를 인접 행렬로 다시 표현할 수 있지만 그건 메모리 소모가 큼(정점의 개수만큼 배열의 크기가 커지기 때문)
- 따라서 인접 행렬보다 인접 리스트의 형태가 더 효율적일 때가 많음
그래프 구조 예
'''
5
8
1 2
1 3
1 5
2 3
2 5
3 4
3 5
4 5
'''
N = int(input())
M = int(input())
arr = [[] for _ in range(N+1)]
for _ in range(M):
u, v = map(int, input().split())
arr[u].append(v)
arr[v].append(u)
'''
[]
[2, 3, 5]
[1, 3, 5]
[1, 2, 4, 5]
[3, 5]
[1, 2, 3, 4]
'''
# DFS
visited = [False] * (N+1)
def dfs(node):
print(node)
visited[node] = True
for a in arr[node]:
if not visited[a]:
dfs(a)
dfs(1)
# 1 2 3 4 5 순으로 탐색
# BFS
from collections import deque
def bfs(start):
visited = [False] * (N + 1)
que = deque()
que.append(start)
visited[start] = True
while que:
node = que.popleft()
print(node)
for a in arr[node]:
if not visited[a]:
que.append(a)
visited[a] = True
bfs(1)
# 1 2 3 5 4 순으로 탐색
'🏷️CS > Algorithm' 카테고리의 다른 글
[코테 스터디] 3주차 : 그리디 (0) | 2024.06.24 |
---|---|
[코테 스터디] 2주차 : 시간복잡도 (0) | 2024.06.17 |
[코테 스터디] 1주차 : 자료구조 / 이진탐색 (1) | 2024.06.10 |
[백준] 1966 (프린터 큐) (2) | 2023.07.26 |
[백준] 구현 2941 / 1193 / 2775 (1) | 2023.05.13 |