참고 자료: 파이썬으로 배우는 자료 구조 핵심 원리(양태환)
6.1 그래프 용어 정리
그래프는 정점(vertex)과 에지(edge)로 이루어진다.
vertex는 어떤 대상의 객체를 말하고 edge는 그 vertex를 잇는 선을 말한다.
이 vertex의 집합을 V(G), edge의 집합을 E(G)라고 한다.
무방향 그래프인 경우에는 G = (V,E), 방향 그래프인 경우에는 G = {V,E}라고 표기한다.
아래에서부터는 그래프에 사용되는 용어들에 대해 정리해보자.
무방향 그래프(undirected graph)
그림과 같이 방향이 없는 그래프를 무방향 그래프라고 한다.
무방향 그래프에서는 edge의 방향이 없으므로 (0,1)과 (1,0)이 같다.
따라서 vertex의 개수가 n개라면 그 그래프의 최대 edge 개수는 n*(n-1)/2가 된다.
방향 그래프(directed graph)
그림과 같이 방향이 있 그래프를 방향 그래프라고 한다.
방향 그래프에서는 edge의 방향이 있으므로 <0,1>과 <1,0>이 다르다. 방향 그래프는 무방향 그래프와 달리 괄호 '(', ')' 대신 중괄호 '<', '>'를 이용해 edge를 표시한다.
vertex의 개수가 n개라면 그 그래프의 최대 edge 개수는 n*(n-1)가 된다.
자기 간선(self-edge, self-loop)
자기 간선은 자기 자신을 가리키는 edge이다. 그래프는 일반적으로 self-loop를 갖지 못한다.
멀티 그래프(multi-graph)
같은 edge가 여러 개 존재하는 그래프를 멀티 그래프라고 한다.
아래의 그래프에서는 <3,2>에 해당하는 edge가 네 개나 존재하는데 이렇게 동일한 edge가 여러 개 존재하는 경우가 멀티 그래프에 해당한다.
그래프에서는 일반적으로 edge 중복을 인정하지 않지만 이를 인정하는 자료 구조를 멀티 그래프라고 한다.
인접(adjacent)
vertex u와 v 사이에 edge (u,v)가 있을 때 u와 v는 서로 인접한다고 표현한다.
경로(path)
경로는 연결되어 있는 vertex를 나열한 것이다.
단순 경로(simple path)는 어떤 경로에서 처음과 마지막을 제외하고 모든 vertex가 다를 때를 의미한다.
사이클(cycle)은 단순 경로에서 처음과 마지막 vertex가 같은 것으로, 결국 같은 vertex로 되돌아오는 경로다.
연결된 그래프(connected graph)
연결된 그래프란 어떤 두 vertex를 고르더라도 항상 연결되어 있는 그래프이다.
어떤 임의의 vertex u와 v를 골랐을 때 u, v 사이에 경로가 있으면 연결되었다고 한다.
차수(degree)
무방향 그래프의 경우, 어떤 vertex v의 차수 d(v)는 vertex v와 incident한 edge 개수이다.
이때 부속되었다(incident)는 표현은 vertex u와 v 사이에 edge (u,v)가 존재할 때 edge (u,v)를 vertex에 incident하다고 표현한다.
방향 그래프에서 차수는 진입 차수와 진출 차수의 합이다.
진입 차수(in-degree)는 vertex v가 head인 경우로, v로 들어오는 edge 개수다. in-d(v)라고 적는다.
진출 차수(out-degree)는 vertex v가 tail인 경우로, v에서 나가는 edge 개수다. out-d(v)라고 적는다.
그리고 이 둘을 합친 차수는 d(v)라고 적는다.
부분 그래프(subgraph)와 신장 부분 그래프(spanning subgraph)
아래와 같은 경우를 부분 그래프라고 한다.
이때 G'는 G의 vertex를 모두 포함하므로 부분 신장 그래프라고 할 수 있다.
6.2 그래프 표현 방법
그래프는 두 가지 방법으로 표현할 수 있다.
하나는 인접 리스트(adjacency list)이고 하나는 인접 행렬(adjacency matrix)이다.
1) 인접 리스트(adjacency list) 표현
인접리스트는 배열 한 개와 각 배열에 연결된 연결리스트들로 구성된다.
그래프의 vertex가 배열의 인덱스가 되고
배열의 각 셀에는 해당 vertex의 인접한 정점의 집합이 연결리스트로 이어진다.
인접 리스트 구현 방법의 빅오를 생각해보자.
1) 어떤 vertex v에 대해 인접한 모든 노드를 탐색하는 연산
이때는 해당 vertex를 인덱스로 한 배열에서 연결리스트를 가져온 후, 그 연결리스트를 순회하면 된다.
모든 vertex을 들릴 필요 없이 해당 vertex의 인접한 vertex만 조사하게 되므로 빅오는 O(d(v))다.
2) vertex u에 대해 edge (u,v)가 그래프에 있는 edge인지 검사하는 연산
이때도 해당 vertex를 인덱스로 한 배열에서 연결리스트를 가져와 그 연결리스트를 순회하므로 빅오는 O(d(v))다.
인접 행렬(adjacency matrix) 표현
인접 행렬은 각각의 행을 vertex로 보고 열을 자신을 포함한 다른 vertex라고 두고 이차원 배열을 만든다.
(3행,0열)은 vertex 3과 0 사이의 관계를 의미하며 이때 둘 사이에 edge가 존재하면 1, 존재하지 않으면 0이다.
이차원 배열을 matrix라 할 때 edge (3,0)이 있으면 matrix[3][0] = 1, 없으면 matrix[3][0] = 0이다.
따라서 아래와 같은 무방향 그래프에서는 대각선에 대해 대칭인 행렬이 나오게 된다.
인접 행렬 구현 방법의 빅오를 생각해보자.
1) 어떤 vertex v에 대해 인접한 모든 노드를 탐색하는 연산
이차원 배열을 사용하는 인접 행렬에서는 v행의 모든 열을 검사해야 한다.
열의 개수는 vertex의 개수이므로 vertex의 개수가 n일 때 O(n)이다.
2) vertex u에 대해 edge (u,v)가 그래프에 있는 edge인지 검사하는 연산
matrix[u][v]의 값이 1인지, 0인지 확인하면 되므로 O(1)이다.
인접 리스트를 이용한 그래프 구현
무방향 그래프를 인접 리스트로 구현해보자.
그래프 ADT
### 그래프 ADT ###
# Object
: 정점 집합 V와 정점 집합 V에 속하는 u,v에 대해 (u,v)가 속하는 에지 집합 E로 구성된 튜플 G = (V,E)
# Operation
1. G.is_empty() -> Boolean
: 비어 있으면 True, 아니면 False
2. G.add_vertex() -> Integer
: 정점을 추가하고 정점 인덱스를 반환
3. G.delete_vertex(v)
: 정점 v를 삭제
4. G.add_edge(u,v)
: 에지 (u,v)를 추가
5. G.delete_edge(u,v)
: 에지 (u,v)를 삭제
6. G.adj(v) -> array
: 점점 v에 인접한 정점 집합을 동적 배열로 반환인접 리스트의 배열 요소로는 연결 리스트를 사용하지만 동적 배열로도 충분히 구현할 수 있다.
그래서 동적 배열로 인접 리스트를 구현해볼 것이다.
Graph 클래스 정의
그래프 객체를 만들 때 매개변수로 vertex의 개수를 받도록 한다.
# 인접 리스트 - 동적 배열 구현
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)]- class Graph 멤버
- vtx_num
- vertex의 개수
- vtx_arr
- vertex의 존재 여부를 나타내는 배열
- 배열의 각 인덱스는 vertex를 나타냄
- 해당 인덱스의 값이 True: 그 vertex가 존재함
- 해당 인덱스 값이 False: 그 vertex가 존재하지 않음
- ex) vtx_arr[0]가 True: vertex 0이 존재
- adj_list
- 각 vertex의 인접한 vertex를 저장하는 인접 리스트
- 각 인덱스는 그래프의 vertex를 나타내고, 해당 인덱스의 리스트에는 해당 vertex와 인접한 vertex의 정보가 담김
- ex) adj_list[0]: vertex 0과 인접한 vertex들의 리스트
vtx_arr로 vertex를 따로 관리하는 이유는 효율성을 위한 것이다.
만약 인덱스 3의 정점이 delete_vertex()로 삭제되었다고 해보자.
vtx_arr를 사용하지 않고 adj_list만 사용한다면 인덱스 3보다 뒤에 있는 vertex가 한 칸씩 당겨져야 할 것이다.
그리고 한 칸씩 당겨진 vertex를 adj_list의 모든 리스트를 순회하면서 인덱스 3보다 큰 vertex를 한 칸씩 당기며 수정해주어야 한다.
반면에 vtx_arr를 함께 사용한다면 인덱스 3의 정점을 삭제하였을 때 vtx_arr의 인덱스 3을 False로 바꾸면 된다.
그리고 adj_list의 모든 리스트를 순회하면서 인덱스 3에 해당하는 요소만 remove 해주면 된다.
후자의 방법이 훨씬 간단하고 효율적이다.
연산 메서드 구현
1. add_vertex()
self.vtx_arr를 순회하면서 비활성화(False)된 vertex가 있으면 이를 사용하고
모두 사용 중이면 vertex를 새롭게 하나 추가한다.
수행이 끝나면 추가된 vertex의 인덱스를 반환한다.
def add_vertex(self):
for i in range(len(self.vtx_arr)):
# 중간에 삭제된 정점이 있을 경우 재사용 함
# vtx_arr 값이 False: 삭제된 정점이라는 뜻
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 - 12. delete_vertex(v)
vtx_arr의 인덱스 v가 False면 해당 인덱스의 vertex가 존재하지 않는다는 경고문을 출력하고,
vtx_arr의 인덱스 v가 True면 adj_list의 인덱스 v 요소를 빈 리스트로 초기화한다.
그리고 vtx_num을 하나 줄이고, vtx_arr[v]를 False로 수정한다.
그리고 adj_list의 모든 리스트를 순회하면서 vertex v를 가졌다면 모두 삭제해준다.
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
# 나머지 정점 중 v와 인접한 정점이 있으면 그 정점의 리스트에서 v 제거
for adj in self.adj_list:
for vertex in adj:
if vertex == v:
adj.remove(vertex)3. add_edge(u,v), delete_edge(u,v)
edge를 추가하고 삭제한다.
edge를 추가할 때에는 adj_list의 인덱스 u에 해당하는 리스트 마지막에 v를 추가하고 인덱스 v에 해당하는 리스트 마지막에는 u를 추가한다.
edge를 삭제할 때에는 adj_list의 인덱스 u에 해당하는 리스트 중 v를 삭제하고 인덱스 v에 해당하는 리스트 중 u를 삭제한다.
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)4. adj(v)
vertex v에 인접한 모든 집합을 리스트로 반환한다.
def adj(self, v):
return self.adj_list[v]show_graph(g)
전체 그래프 출력
# 그래프를 편하게 보기 위한 편의 함수
def show_graph(g):
print(f"num of vertices : {g.vtx_num}")
print("vertices : {", end="")
for i in range(len(g.vtx_arr)):
if g.vtx_arr[i]:
print(f"{i}, ", end="")
print("}")
for i in range(len(g.vtx_arr)):
if g.vtx_arr[i]:
print(f"[{i}] : {{", end="")
for j in g.adj_list[i]:
print(f"{j}, ", end=" ")
print("}")전체 코드
'''
### 그래프 ADT ###
# Object
: 정점 집합 V와 정점 집합 V에 속하는 u,v에 대해 (u,v)가 속하는 에지 집합 E로 구성된 튜플 G = (V,E)
# Operation
1. G.is_empty() -> Boolean
: 비어 있으면 True, 아니면 False
2. G.add_vertex() -> Integer
: 정점을 추가하고 정점 인덱스를 반환
3. G.delete_vertex(v)
: 정점 v를 삭제
4. G.add_edge(u,v)
: 에지 (u,v)를 추가
5. G.delete_edge(u,v)
: 에지 (u,v)를 삭제
6. G.adj(v) -> array
: 점점 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] == 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
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
# 나머지 정점 중 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]
# 그래프를 편하게 보기 위한 편의 함수
def show_graph(g):
print(f"num of vertices : {g.vtx_num}")
print("vertices : {", end="")
for i in range(len(g.vtx_arr)):
if g.vtx_arr[i]:
print(f"{i}, ", end="")
print("}")
for i in range(len(g.vtx_arr)):
if g.vtx_arr[i]:
print(f"[{i}] : {{", end="")
for j in g.adj_list[i]:
print(f"{j}, ", end=" ")
print("}")실행 코드
if __name__=="__main__":
g=Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(0, 3)
g.add_edge(1, 2)
g.add_edge(2, 3)
show_graph(g)
print()
added=g.add_vertex()
g.add_edge(added, 1)
g.add_edge(added, 2)
show_graph(g)
print()
g.delete_vertex(2)
show_graph(g)
print()
added=g.add_vertex()
print(added)
g.add_edge(added, 1)
g.add_edge(added, 4)
show_graph(g)
print()위의 코드를 실행하면 아래와 같은 결과를 얻을 수 있다.
num of vertices : 4
vertices : {0, 1, 2, 3, }
[0] : {1, 2, 3, }
[1] : {0, 2, }
[2] : {0, 1, 3, }
[3] : {0, 2, }
num of vertices : 5
vertices : {0, 1, 2, 3, 4, }
[0] : {1, 2, 3, }
[1] : {0, 2, 4, }
[2] : {0, 1, 3, 4, }
[3] : {0, 2, }
[4] : {1, 2, }
num of vertices : 4
vertices : {0, 1, 3, 4, }
[0] : {1, 3, }
[1] : {0, 4, }
[3] : {0, }
[4] : {1, }
2
num of vertices : 5
vertices : {0, 1, 2, 3, 4, }
[0] : {1, 3, }
[1] : {0, 4, 2, }
[2] : {1, 4, }
[3] : {0, }
[4] : {1, 2, }그리고 노드 간 연결 상태를 시각적으로 확인해보면 아래와 같이 잘 연결된 것을 확인할 수 있다.
6.3 그래프 순회
그래프는 선형 자료 구조가 아니기에 모든 노드를 순회하기 위해서는 특별한 순회 방법이 필요하다.
두 가지 방법이 있는데 하나는 너비 우선 탐색(BFS)이고 다른 하나는 깊이 우선 탐색(DFS)이다.
너비 우선 탐색은 큐로 구현하고 깊이 우선 탐색은 스택을 기반으로 한다.
1) 너비 우선 탐색(Breadth First Search, BFS) 개념
너비 우선 탐색(BFS)은 출발 vertex v를 방문한 후(L1) v에 인접한 모든 vertex가 이루는 L2의 vertex를 모두 방문한다. 그리고 L2의 vertex에서 인접한 vertex가 이루는 L3의 모든 vertex를 방문한다.
이런 식으로 진행하여 모든 정점을 방문할 때까지 반복한다.
BFS 구현
앞서 말했듯, BFS는 큐를 사용한다. 파이썬이 제공하는 큐를 사용하여 구현해보자.
Graph 클래스 정의
파이썬 queue 모듈에서 Queue 클래스를 import 한다.
enqueue 연산은 put() 메서드로, dequeue 연산은 get() 메서드로 수행할 수 있다.
- class Graph 멤버
- adj_list
- 인접 리스트
- visited
- 인덱스에 해당하는 vertex의 방문 여부에 대한 배열
- 해당 vertex를 방문했다면 True, 방문하지 않았다면 False를 저장
- init_visited() 메서드로 visited 멤버를 모두 False로 초기화한다.
- 인덱스에 해당하는 vertex의 방문 여부에 대한 배열
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] = FalseBFS 구현
우선 큐를 하나 만들고 init_visited() 메서드로 방문 리스트를 모두 False로 초기화한다.
그리고 매개변수로 들어온 시작 vertex v부터 큐에 삽입하고 방문 리스트의 인덱스 v 값을 True로 바꿔준다.
그리고 큐가 빌 때까지 계속 while문을 실행하며 모든 vertex를 방문한다.
반복문에서는
큐에서 dequeue하고 그 값을 인덱스로 하는 vertex에 방문한다. 방문한 vertex에서 특정 연산을 수행한다.(아래 코드에서는 vertex를 출력하는 것으로 연산을 대신하였다.)
방문한 후, 방문한 vertex v를 인덱스로 하는 인접 리스트를 가져와 adj_v에 저장한다.
그리고 adj_v의 각 값을 u에 할당하면서 순회한다.
만약 방문리스트의 인덱스 u 값이 False라면, 즉 아직 vertex u에 방문하지 않았다면,
vertex u를 큐에 삽입하고 방문 리스트의 인덱스 u 값을 True로 바꿔준다.
아직 모든 vertex를 방문하지 않았다면 adj_v의 모든 요소를 다 돌았을 때 큐가 다시 채워지게 된다.
이 과정을 큐가 빌 때까지 반복하면 모든 vertex를 방문할 수 있다.
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[u] = True위의 과정을 그림으로 아래와 같이 표현할 수 있다.
2) 깊이 우선 탐색(Depth First Search, DFS) 개념
BFS는 시작 vertex를 기준으로 인접한 vertex를 차례로 방문하며 진행되었다.
DFS는 시작 vertex에서 한 방향을 정하고 그 방향으로 쭉 따라간 후 더 이상 갈 vertex가 없으면 다시 시작 vertex로 돌아와 아직 방문하지 않은 방향으로 쭉 따라가는 식으로 진행된다.
그림에서처럼 시작 vertex가 3이면 0인 vertex 쪽으로 쭉 따라간다.
1인 vertex에 다다라 더 갈 곳이 없으면 다시 시작 vertex로 돌아온다.
그리고 아직 가보지 않은 4인 vertex 쪽으로 따라가고 다시 시작 vertex인 3에 다다라 더 이상 갈 곳이 없으면 종료된다.
중요한 점은 반드시 시작 vertex로 돌아온 후 더 갈 곳이 없어야만 실행이 종료된다는 것이다.
깊이 우선 탐색은 스택을 사용한다.
그리고 이 스택은 재귀 함수를 호출하는 형태로 구현할 수 있다.
DFS 구현 - 재귀
우선 dfs()로 visited 배열을 초기화해준다.
그리고 __dfs_recrusion()에 매개변수 v를 입력하여 실행한다.
방문을 한 후 visited[v]를 True로 만들고 vertex v의 인접리스트를 구한다.
인접리스트 adj_v[v]를 순회하며 방문하지 않은 vertex을 방문할 때는 그 vertex를 인수로 해서 __def_recursion()을 호출한다.
class Graph:
def __init__(self, vertex_num):
#인접 리스트로 구현
self.adj_list=[[] for _ in range(vertex_num)]
#방문 여부 체크
self.visited=[False for _ in range(vertex_num)]
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)위의 과정을 그림으로 아래와 같이 표현할 수 있다.
(1)
시작 vertex은 2로,
맨 처음 __dfs_recursion(2)를 호출한다.
visited[2]를 True로 만들고 adj[2] = {1,3}이다.
1과 3중 한 방향을 선택하게 되는데 여기서는 vertex 1을 선택했다고 가정하자.
(2)
그다음 __dfs_recursion(1)을 호출하여 vertex 1에 방문한다.
visited[1]를 True로 만들고 adj[1] = {0,2}이다.
2는 이미 방문했으므로 vertex 0을 선택한다.
(3)
__dfs_recursion(0)을 호출하여 vertex 0에 방문한다.
visited[0]을 True로 만들고 adj[0] = {1}이다.
그런데 vertex 1은 이미 방문했기 때문에 더이상 이동할 수 있는 vertex가 없다.
그렇다면 vertex 0으로 오기 전 vertex 1로 돌아가야 한다.
이는 현재 함수를 종료함수로서 수행할 수 있다. 현재 함수를 종료하면 vertex 1로 돌아갈 수 있다.
(4)
vertex 1로 돌아온 상태이다.
adj[1] = {0,2}가 모두 방문한 상태이므로 이 함수 역시 종료된다.
함수가 종료되면 vertex 2로 돌아간다.
(5)
vertex 2에 돌아온 모습이다.
adj[2] = {1,3}에서 1 방향으로 끝까지 따라갔다 온 것이다.
이제 남은 방향인 3 방향으로 따라가야 한다.
(6)
__dfs_recursion(3)를 호출하여 vertex 3에 방문한다.
visited[3] = True로 만들고 adj[3] = {2}는 이미 방문했으므로 함수를 종료시킨다.
visited를 보면 모든 노드를 방문했다는 것을 알 수 있지만,
시작 vertex로 돌아가 더 이상 따라갈 vertex가 없을 때 알고리즘을 종료한다.
(7)
adj[2] = {1,3}을 보면 시작 vertex에 인접한 모든 vertex를 방문했다는 것을 알 수 있다.
for 문이 종료되며 함수 실행이 종료되고,
마지막 남은 스택 프레임이 사라지며 알고리즘이 종료된다.
'Algorithm > 알고리즘' 카테고리의 다른 글
| [휴학 중 코테 부수기] # 2. 그리디 알고리즘 (6) | 2023.10.23 |
|---|---|
| [BOJ](Python) 백준 2075번 N번째 큰 수 (0) | 2023.09.26 |
| [알고리즘](Python) 백준 2696번 중앙값 구하기 - 우선순위 큐 (0) | 2023.09.19 |
| [알고리즘](Python) 트리 (1) | 2023.09.12 |
| [알고리즘](Python) 백준 10828번 - 스택 (0) | 2023.09.12 |
