오늘은 알고리즘/자료구조를 공부하면서 평소 두려움에 떨며 제대로 공부하지 못했던 그래프에 대해 공부를 하며 정리해보았습니다. 공부하며 작성한 글이므로 반말이어도 양해부탁드립니다.
그래프
는 가장 일반화된 자료구조로, 연결된 객체들 사이의 관계를 잘 표현함.그래프 이론
이라고 함.모든 다리를 한번만 건너서 출발했던 장소로 돌아올 수 있는가?
라는 문제가 답이 존재하지 않는다는 것을 그래프 이론을 통해 증명함.그래프
는 아래 두가지(정점, 간선)의 집합으로 구성됨 무방향 그래프 (undirected graph)
방향 그래프 (directed graph)
가중치 그래프 (weighted graph)
부분 그래프 (subgraph)
인접행렬(Adjacency matrix)
을 사용하여 표현함인접리스트(Adjacency list)
라고 함그래프 탐색
은 가장 기본적인 연산으로 하나의 정점에서 시작하여 모든 정점들을 한번씩 방문하는 작업을 의미함깊이 우선 탐색
과 너비 우선 탐색
의 두가지가 존재함🎁 여기서 잠깐!
파이썬은 collections라는 모듈에서 defaultdict, Counter, deque 등의 기능을 제공하는데, 이중deque
와defaultdict
를 사용하면 유용하게 각각 BFS와 DFS를 정의할 수 있다!
- deque : 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너
- Counter : 해시 가능한 객체를 세는 데 사용하는 딕셔너리 서브 클래스
- OrderedDict : 항목이 추가된 순서를 기억하는 딕셔너리 서브 클래스
- defaultdict : 누락된 값을 제공하기 위해 팩토리 함수를 호출하는 딕셔너리 서브 클래스
from collections import deque
from collections import defaultdict
# defaultdict를 이용하는 경우
a = defaultdict(list) # list형식으로 저장해주겠다는 뜻
# 큐를 이용하는 경우
q = deque()
스택
또는 재귀
을 이용한 미로 탐색과 유사함참고
인접행렬과 재귀를 이용한 DFS
# 이전 방문 여부 확인
check = [False] * (n+1)
# DFS 함수 정의
def dfs(v):
check[v] = True # v노드를 방문함
# 방문 가능한 모든 노드를 전부 순회
for i in range(1, n+1):
# i 조건 : v와 인접해야함 + 이전에 방문한 적이 없어야 함
if arr[v][i] == 1 and check[i] == False:
dfs(i)
# 함수 실행
dfs(v)
인접리스트와 재귀를 이용한 DFS
# 이전에 방문한적이 있었는지 체크
check = [False] * (n+1)
# DFS 함수 정의
def dfs(v):
check[v] = True # v노드를 방문함
# 방문 가능한 모든 노드를 전부 순회
for i in a[v]:
# 인접 리스트는 인접한 정점에 대한 정보만 들어있다.
# 따라서, 이전에 방문한 적이 있었는지만 확인하면 된다.
if check[i] == False:
dfs(i)
# 함수 실행
dfs(v)
인접행렬과 스택을 이용한 DFS
# 이전 방문 여부 확인
check = [False] * (n+1)
stack = deque()
def dfs(start):
check[start] = True
stack.append(start)
# 스택이 비어있으면 종료
while stack:
v = stack.pop()
print(v)
for i in range(n, -1, -1):
if arr[v][i] == 1 and check[i] == False:
check[i] = True
stack.append(i)
dfs(v)
인접리스트와 스택을 이용한 DFS
# 이전에 방문한적이 있었는지 체크
check = [False] * (n+1)
stack = deque()
def dfs(start):
check[start] = True
stack.append(start)
# 스택이 비어있으면 종료
while stack:
v = stack.pop()
print(v)
for i in a[v]:
if check[i] == False:
check[i] = True
stack.append(i)
dfs(v)
참고
인접행렬과 큐를 이용한 BFS
# 이전에 방문한적이 있었는지 체크
check = [False] * (n+1)
# 큐 선언
q = deque()
# BFS정의
def bfs(v):
# 방문 체크
check[v] = True
# 큐에 추가
q.append(v)
# 큐에 더 이상 방문할 노드가 없으면 종료
while q:
# FIFO
pop = q.popleft()
# 방문 가능한 모든 노드를 전부 순회
for i in range(1, n+1):
# i 조건 : pop과 인접해야함 + 이전에 방문한 적이 없어야 함
if arr[pop][i] == 1 and check[i] == False:
check[i] = True
q.append(i)
# 함수 실행
bfs(v)
인접리스트와 큐를 이용한 BFS
# 이전에 방문한적이 있었는지 체크
check = [False] * (n+1)
# 큐 선언
q = deque()
# BFS정의
def bfs(v):
# 방문 체크
check[v] = True
# 큐에 추가
q.append(v)
# 큐에 더 이상 방문할 노드가 없으면 종료
while q:
# FIFO
pop = q.popleft()
# 인접 리스트는 인접한 정점에 대한 정보만 들어있다.
# 따라서, 이전에 방문한 적이 있었는지만 확인하면 된다.
for i in a[v]:
if check[i] == False:
check[i] = True
q.append(i)
# 함수 실행
bfs(v)
긴 글 읽어주셔서 감사합니다 ^~^
좋은 글이네요! GCN GAT에 대해서도 글 써주시면 좋을 거 같아요!