6.1. 용어
그래프는 정점(vertex)의 집합 V(G)와 에지(Edge)의 집합 E(G)로 정의
- G = (V, E)
6.1.1. 무방향 그래프
- G = (V, E)
- V(G) = {0, 1, 2, 3}
- E(G) = {(0,1), (0,2), (0,3), (2,3)}
- 정점의 개수가 n인 경우, 최대 에지의 개수 : n(n-1)/2
- 에지 : 정점과 정점을 잇는 선
6.1.2. 방향 그래프
- G = <V, E>
- V(G) = {0, 1, 2, 3}
- E(G) = {<0,1>, <0,2>, <1,2>, <2,3>, <3,2>}
- 정점의 개수가 n인 경우, 최대 에지의 개수 : n(n-1)
- <0,1> : 0이 head, 1이 tail
6.1.3. 자기 간선
- 정점이 head이자 tail
6.1.4. 멀티그래프
- 중복 에지 인정
6.1.5. 인접
- 정점 u, v 사이에 에지 (u, v) 가 있는 경우, u와 v는 인접하다
- u ∈ V(G), v ∈ V(G)고 (u, v) ∈ E(G)이면 u와 v는 adjacent
6.1.6. 경로
- 경로(path) : (v1, v2), (v2, v3), (v3, v4)가 집합 E(G)의 원소일 때 v1에서 v4까지 정점 순서 v1->v2->v3->v4
- 경로의 길이 = 에지의 개수
6.1.6.1. 단순 경로
- 처음과 마지막 경로가 다름
6.1.6.2. 사이클
- 단순 경로에서 처음과 마지막 경로가 같음
- v2->v3->v4->v2
6.1.7. 연결된 그래프(connected graph)
- 어떤 임의의 정점 u와 다른 어떤 임의의 정점 v를 골랐을 때 정점 사이에 경로가 있으면 이를 연결되었다(connected)
- G = (V, E)
- V(G) = {0, 1, 2, 3, 4, 5, 6, 7}
- E(G) = {(0, 3), (0, 4), (1, 2), (1, 5), (2, 5), (3, 4), (4, 6), (5, 7)}
- 연결요소 : 정점 집합 {0, 3, 4, 6}과 {1, 2, 5, 7}을 각각 연결 요소(connected component)임.
6.1.8. 차수(degree)
1) 무방향 그래프의 차수
- 어떤 정점 v의 차수 d(v)는 정점 v가 부속된 에지 개수
- 부속되었다(incident) : 정점 u와 정점 v 사이에 에지 (u, v)가 존재할 때 에지 (u, v)를 정점 u에 부속되었다, 정점 v에 부속되었다
2) 방향 그래프의 차수
방향그래프의 차수 : 진입차수 + 진출차수 = d(v)
- 진입 차수(in-degree) : 정점 v가 head인 경우 = 정점 v로 들어오는 에지 개수
진입차수 : in-d(v)
- 진출 차수(out-degree) : tail인 경우 = 정점 v에서 나가는 에지 개수
진출 차수 : out-d(v)
6.1.9. 부분 그래프, 신장 부분 그래프
1) 부분 그래프
그래프 G'가 G에 대해 V(G') ⊆ (G)고 E(G') ⊆ E(G)면 그래프 G'는 그래프 G의 부분 그래프
2) 신장 부분 그래프(spanning subgraph)
그래프 G'가 그래프 G에 대해 V'=V고 E(G') ⊆ E(G)를 만족
ex) G'는 V'=V를 만족하므로 신장 부분 그래프이지만, G''에는 정점 3이 누락되었으므로 V'=V를 만족하지 못해서 부분 그래프이지만 신장 부분 그래프는 아님
6.2. 그래프 표현 방법 : 인접리스트, 인접 행렬
1) 인접 리스트(adjacency list)
- 배열 1개와 연결리스트들로 구성
- 배열의 인덱스 = 정점
- 연결리스트 : 해당 정점에 인접한 정점의 집합
ex) 정점 0에 연결된 정점이 1,3 인 경우 리스트 요소는 1,3O(d(v))
1) 어떤 정점 v에 대해 인접한 모든 노드를 탐색 : 해당 정점을 인덱스로 삼아 해당되는 연결리스트를 통해 순회하므로, 모든 정점을 조사할 필요 없이 해당 정점의 인접한 정점들만 조사
2) 정점 u에 대해 (u, v) ∈ E(G)인지를 검사 : 해당 정점을 인덱스로 연결 리스트를 가져와 인접한 모든 노드를 순회해야 함.
1-1) ADT
1. Object
- 정점 집합 V와 정점 집합 V에 속하는 u, v에 대해 (u, v)가 속하는 에지 집합 E로 구성된 튜플 G = (V, E)
2. Operation
- G.is_empty() : Boolean
- G.add_vertex() : 정점 추가하고 정점 인덱스 반환(Integer)
- G.delete_vertex(v) : 정점 v 삭제
- G.add_edge(u, v) : 에지 (u, v) 추가
- G.delete_edge(u, v) : 에지 (u, v) 삭제
- G.adj(v) : 정점 v에 인접한 정점 집합을 동적 배열로 반환
1-2) 구현
class Graph:
def __init__(self, vertex_num = None):
self.adj_list = []
self.vtx_num = 0 #정점의 개수
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)] #연결리스트 대신 동적배열 사용- vtx_arr : delete_vertex() 사용 시 도중에 있던 정점이 사라질 수 있기 때문에 이를 방지하기 위한 배열
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)): # 중간에 삭제된 정점이 있는지 확인
if self.vtx_arr[i] == False: #삭제된 정점이라는 의미임
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- add_vertex() : 모든 정점을 순회하면서 비활성화된 정점이 있다면 사용하고, 모두 사용 중이라면 정점을 추가함.
def delete_vertex(self, v) :
if v >= self.vtx_num :
raise Exception(f"There is no vertex of {v}")
if self.vtx_arr[v]:
self.adj_list[v] = []
self.vtx_num -= 1
self.vtx_arr[v] = False
for adj in self.adj_list:
for vertex in adj:
if vertex == v:
adj.remove(vertex)- 정점 v 삭제 = 비활성화
if self.vtx_arr[v] : self.adj_list[v] = []:해당 정점이 있다면 인접리스트 초기화self.vtx_arr[v] = False: 해당 정점 비활성화, 추후 활성화하여 사용 가능하도록 비활성화for adj in self.adj_list: for vertex in adj:
: 이중루프를 돌면서 해당 정점과 이어져 있던 에지들 삭제
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]- 해당 정점 v에 인접한 모든 노드 집합을 리스트로 반환
2) 인접 행렬(adjacency matrix)
- 행 : 정점
- 열 : 자신을 포함한 다른 정점
ex) 1행 2열 = 정점 1과 정점 2의 관계 : 해당 값이 0인 경우, 인접하지 않다 - 이차원 배열 adj_matrix : 에지 (0,1)이 있다면 adj_matrix[0][1] = 1, 없다면 0
- 무방향 그래프의 경우, (0,1), (1,0) 모두 존재하므로 행렬에서는 모두 1 : 대각선에 대해 대칭
O(n)
1) 어떤 정점 v에 대해 인접한 모든 노드를 탐색 : v행에 대하여 모든 열 탐색
O(1)
2) (u, v)가 있는지 여부를 확인하는 연산 : adj_matrix[u][v] 유무 확인
5.3. 그래프 순회(traversal) : 그래프의 모든 노드 방문
1) 너비 우선 탐색(Breadth First Search, BFS) : 큐 기반
ex) 출발 정점이 3인 경우, 출발 정점을 지나 인접 정점 모두 탐색, 이후 인접 정점들의 인접 정점 탐색 순으로 탐색함
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
- 인접 리스트로 구현
- visited 변수 : 정점의 방문 여부 확인 -> 각 정점 방문 시, True 반환, 미방문 시 False 반환
def bfs(self, v):
q = Queue()
self.init_visited() # 방문 체크리스트 초기화
q.put(v) # 첫 번째 정점을 큐에 넣음
self.visited[v] = True # 첫 번째 정점 방문 완료
while not q.empty():
v = q.get() # 이미 방문한 정점 dequeue
print(v, end='=')
adj_v = self.adj_list[v] #이미 방문한 정점의 인접 정점 리스트
for u in adj_v:
if not self.visited[u]:
q.put(u)
self.visited[u] = True
- 큐 생성 후, 매개변수로 전달된 시작 정점을 삽입하고 큐가 비기 전까지 while문을 통해 모든 정점을 방문함.
q = Queue(): 큐 생성self.init_visited(): 모든 정점에 대해 방문 기록 초기화q.put(v): 정점 v를 q에 넣음self.visited[v] = True: 해당 정점 방문 완료while not q.empty():: q가 빌 때까지 while 루프를 돌면서 모든 정점 방문v = q.get(): get()을 통해 dequeue로 q의 front값을 pop하면서 그 값을 다음 정점으로 선정adj_v = self.adj_list[v]: adj_v는 해당 정점 v에 대한 인접한 모든 정점- for문을 순회하며 방문하지 않은 정점을 큐에 넣고, 최초 v의 인접 정점의 방문 여부 True로 변경함.
ex) 0-2-1-3으로 된 그래프에서 2가 시작점이었다면, 2를 dequeue 하면서 queue에는 0과 1이 삽입됨. 0이 dequeue될 때는 0과 연결된 인접 정점이 없으므로 그대로 dequeue되며, 1의 경우 3을 삽입 후 dequeue됨. 3이 dequeue될 경우에도 인접 정점이 없으므로 dequeue된 후, 큐는 비게 되어 루프 종료 = 모든 정점 방문 완료
2) 깊이 우선 탐색(Depth First Search, DFS) : 스택 기반
시작 정점을 기준으로 인접한 모든 노드를 방문 후, 다시 시작 정점으로 돌아와 가보지 않은 방향으로 다시 방문
2-1) 재귀 함수를 이용(스택프레임)
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)- dfs : 재귀함수를 돌기 전 방문리스트를 초기화함.
- __dfs_recursion : 매개변수 v를 먼저 방문 후, v와 인접한 adj_v의 리스트에 있는 모든 정점을 방문함. 방문하지 않은 정점을 만날 때는 재귀 함수 호출
ex) 0-1-2-3으로 된 그래프에서 2를 시작 정점으로 하는 경우 : dfs_rec(2)를 시작하면서 True로 변경, adj[2] = {1,3}이며 for 루프를 돌면서 dfs_rec(1), dfs_rec(0)을 돈 후, dfs_rec(3)까지 방문 후 종료.
-> 스택프레임 구조 : dfs_rec(2)-dfs_rec(1)-dfs_rec(0) -> dfs_rec(2)-dfs_rec(3) -> dfs_rec(2) -> None - 재귀 함수가 끝난 경우 반드시 시작 정점으로 돌아가며, 더이상 방문할 곳이 없는 경우 종료됨
2-2) 스택과 반복문 이용
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.peak()
adj_v = self.adj_list[v]
for u in adj_v:
if not self.visited[u]:
s.push(u)
self.visited[u] = True
is_visited = True
break
if not is_visited:
s.pop()
s.push(v): 최초 방문한 정점을 stack에 쌓음is_visited = False: 아직 방문하지 않은 정점을 방문하였는가?v = s.peak(): dfs와는 다르게 dequeue를 통해 정점을 가져오지 않고 peak 메서드 사용하여 스택에는 정점이 그대로 쌓여있음is_visited = True break: 인접 정점들에 대해 순회하며 방문하지 않은 정점을 만난 경우 True로 변경 후, 방문하지 않았던 정점에 대하여 for문을 빠져나가 while 루프를 다시 돈다.- for 문 빠져나가는 법
1) is_visited = True : 방문하지 않은 정점을 발견하여 이동한 경우 -> 스택에는 이동한 정점이 쌓여 있음. -> 다음 모든 정점 방문 후 pop()을 통해 해당 정점을 삭제 후 이전 정점으로 이동할 수 있음.
2) is_visited = False : adj[v]의 모든 노드를 방문한 상태 -> 이전 정점으로 이동해야하므로 현재 정점을 pop해야함
2-3) 그래프가 연결되어 있지 않은 경우
def dfs_all(self):
self.init_visited()
for i in range(len(self.visited)):
if not self.visited[i]:
self.__dfs_recursion(i)- 그래프가 연결되어 있지 않더라도 모든 정점 순회 가능함.
- self.visited의 길이 만큼 반복문을 돌기 때문에 연결되어있지 않은 그래프들의 모든 정점 방문이 가능함.
hello world!