이번 그래프는 단순하게 생성자에서 정점을 만들고 add_edge() 메서드에서 에지를 추가합니다. 생성자를 보면 visited라는 멤버를 확인할 수 있는데 BFS와 DFS 모두에서 정점의 방문 여부를 확인할 수 있는 매우 중요한 배열입니다. 각 정점을 방문했다면 True를 반환하고, 아직 방문하지 않았다면 False를 반환합니다. init_visited() 메서드는 visited 멤버의 모든 요소를 False로 만듭니다. 먼저 코드를 보겠습니다.
코드 6-7
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