코드 6-1
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)]
코드 6-1을 보면 그래프 객체를 만들 때 매개변수로 정점 개수를 받도록 합니다. adj_list는 인접 리스트입니다. vtx_num은 정점 개수를 나타내고, vtx_arr은 정점의 존재 여부를 저장합니다. vtx_arr이 필요한 이유는 delete_vertex() 메서드로 도중에 있던 정점이 사라질 수 있기 때문입니다. 정점을 삭제할 때마다 뒤에 있는 모든 정점을 한 칸씩 당긴다면 인접 리스트의 모든 요소를 순회하면서 당겨진 정점을 모두 변경해 주어야 합니다. 이는 효율적이지 못하지요. delete_vertex() 메서드를 호출할 때 단순히 그 정점 인덱스를 비활성화한다면 훨씬 편하지 않을까요?