먼저 보면 좋은 자료 → 자료구조 | 그래프 1
1. 인접 리스트와 인접 행렬
그래프를 표현하는 방법으로 인접 리스트(adjacency list)와 인접 행렬(adjacency matrix)가 있다.
1-1. 인접 리스트
인접 리스트는 그래프의 연결 관계를 vector의 배열로 나타내는 방식
배열 한 개와 연결 리스트들로 구성
-
정점이 배열의 인덱스 역할
-
배열의 요소는 연결 리스트이며, 해당 정점의 인접한 정점 집합
-
정점 v에 대해 인접한 모든 노드를 탐색하는 연산 → O(d(v))
-
정점 u에 대해 (u, v)∈E(G)인지 확인하는 연산 → O(d(v))
1-2. 인접 행렬
그래프의 연결 관계를 이차원 배열로 나타내는 방식
-
무방향 그래프의 경우 대각선에 대해 대칭
-
정점 v에 대해 인접한 모든 노드를 탐색하는 연산 → O(n)
-
정점 u에 대해 (u, v)∈E(G)인지 확인하는 연산 → O(1)
2. 인접 리스트로 무뱡향 그래프 구현
그래프 알고리즘을 공부할 때는 그래프가 한 번 완성되면 이후에는 정점 또는 에지가 거의 변하지 않기 때문에 해당 연산들이 크게 필요하진 않지만 전체 구조를 파악하기 위해 구현 해본다 !
-
G.is_empty(): 비어 있으면 True, 아니면 False 반환 -
G.add_vertext(): 정점을 추가하고 정점 인덱스를 반환 -
G.delete_vertex(v): 정점 v를 삭제 -
G.add_edge(u, v): 에지(u, v) 추가 -
G.delete_edge(u, v): 에지(u, v) 삭제 -
G.adj(v): 정점 v에 인접한 정점 집합을 동적 배열로 반환
class Graph:
def __init__(self, vertex_num=None):
# 인접 리스트
self.adj_list = []
self.vtx_num = 0
# 정점이 있으면 True
# 정점이 없다면 False
self.vtx_arr = []
# 정점 개수를 매개변수로 넘기면
# 초기화 진행
if vertex_num:
self.vtx_num = vertex_num
self.vtx_arr = [True for _ in range(self.vtx_num)]
# 배열 요소로 연결 리스트 대신 동적 배열을 사용
self.adj_list = [[] for _ in range(self.vtx_num)]
def is_empty(self):
if self.vtx_num == 0:
return True
return False
def add_vertex(self):
for i in range(len(self.vtx_arr)):
# 중간에 삭제된 정점이 있을 경우 재사용
# vtx_arr 값이 False면 삭제된 정점이라는 의미
if self.vtx_arr[i] == Flase:
self.vtx_num += 1
self.vtx_arr[i] = True
return i
self.adj_list.append([])
self.vtx_num += 1
self.vtx_arr.append(True)
return self.vtx_num - 1
def delete_vertex(self, v):
if v >= self.vtx_num:
raise Exception(f"There is no vertex of {v}")
# 정점 v가 있으면
if self.vtx_arr[v]:
# 정점 v의 인접 정점 집합을 초기화
self.adj_list[v] = []
self.vtx_num -= 1
self.vtx_arr[v] = False
# 나머지 정점 중 v와 인접한 정점이 있다면 그 정점 리스트에서 v 제거
for adj in self.adj_list:
for vertex in adj:
if vertex == v:
adj.remove(vertex)
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def delete_edge(self, u, v):
self.adj_list[u].remove(v)
self.adj_list[v].remove(u)
def adj(self, v):
return self.adj_list[v]3. 그래프 순회(traversal)
모든 노드를 순회하는 방법으로는 너비 우선 탐색과 깊이 우선 탐색이 있다.
-
너비 우선 탐색(breadth first search, BFS): 큐를 이용하여 구현
-
깊이 우선 탐색(depth first search, DFS): 스택 기반
3-1. BFS 순회
너비를 우선으로 탐색 (수평적 탐색)
from queue import Queue
class Graph:
def __init__(self, vertex_num):
# 인접 리스트로 구현
self.adj_list = [[] for _ in range(vertex_num)]
# 방문 여부 체크
self.visited = [False for _ in range(vertex_num)]
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def init_visited(self):
for i in range(len(self.visited)):
self.visited[i] = False
def bfs(self, v):
q = Queue()
# 방문 체크 리스트 초기화
self.init_visited()
# 첫 번째 정점을 큐에 넣고 방문 체크
q.put(v)
self.visited[v] = True
while not q.empty():
v = q.get()
# 방문
print(v, end=" ")
# 인접 리스트 얻어오기
adj_v = self.adj_list[v]
for u in adj_v:
if not self.visited[u]:
q.put(u)
self.visited[v] = True
3-2. DFS 순회
깊이를 우선적으로 탐색 (수직적 탐색)
-
스택 기반
-
재귀함수 호출 형태 → 스택 프레임
-
스택 자료구조의 명시적 사용
-
- 시작 정점으로 돌아가 시작 정점에서 더 이상 따라갈 정점이 없을 때 알고리즘 종료
# 스택 프레임을 이용한 dfs
class Graph:
def __init__(self, vertex_num):
# 인접 리스트로 구현
self.adj_list = [[] for _ in range(vertex_num)]
# 방문 여부 체크
self.visited = [False for _ in range(vertex_num)]
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def init_visited(self):
for i in range(len(self.visited)):
self.visited[i] = False
# 재귀함수 호출 이용
def __dfs_recursion(self, v):
# 방문
print(v, end=" ")
# 방문 체크
self.visited[v] = True
adj_v = self.adj_list[v]
for u in adj_v:
if not self.visited[u]:
self.__dfs_recursion(u)
def dfs(self, v):
self.init_visited()
self.__dfs_recursion(v)
# 스택 자료 구조와 반복문을 활용한 구현
def iter_dfs(self, v):
s = Stack()
self.init_visited()
s.push(v)
# 방문 체크 및 방문
self.visited[v] = True
print(v, end=" ")
# 아직 방문하지 않은 정점을 방문했는가
is_visited = False
while not s.empty():
is_visited = False
v = s.peek()
# 인접 리스트 받아오기
adj_v = self.adj_list[v]
for u in adj_v:
if not self.visited[u]:
s.push(u)
# 방문 체크 및 방문
self.visited[u] = True
print(u, end=" ")
# 아직 방문하지 않은 정점을 방문했으므로
is_visited = True
break
if not is_visited:
s.pop()
# 그래프가 연결되어 있지 않은 경우 고려하기
def dfs_all(self):
self.init_visited()
for i in range(len(self.visited)):
if not self.visited[i]:
self.__dfs_recursion(i)
