◼︎ 15-2 그래프 탐색 과정

이해를 돕기 위해 큐와 집합의 상태 변화를 함께 표시하였습니다. 종이에 그래프를 그린 다음 큐와 집합도 함께 적으면서 따라가 보세요.

 

 

① 시작 꼭짓점을 qu와 done에 각각 추가하고 시작합니다. → qu = [1], done = {1}

② qu에서 1을 꺼내 출력합니다. → qu = [], done = {1}

③ 1에 연결된 2, 3을 qu와 done에 추가합니다. → qu = [2, 3], done = {1, 2, 3}

④ qu에서 2를 꺼내 출력합니다. → qu = [3], done = {1, 2, 3}

⑤ 2에 연결된 1, 4, 5 중에서 1은 이미 done에 있으므로 중복되지 않도록 제외하고 4, 5를 qu와 done에 추가합니다. → qu = [3, 4, 5], done = {1, 2, 3, 4, 5}

⑥ qu에서 3을 꺼내 출력합니다. → qu = [4, 5], done = {1, 2, 3, 4, 5}

⑦ 3에 연결된 1은 이미 done에 있으므로 추가하지 않습니다.

⑧ qu에서 4를 꺼내 출력합니다. → qu = [5], done = {1, 2, 3, 4, 5}

⑨ 4에 연결된 2는 이미 done에 있으므로 추가하지 않습니다.

⑩ qu에서 5를 꺼내 출력합니다. → qu = [], done = {1, 2, 3, 4, 5}

⑪ 5에 연결된 2는 이미 donee에 있으므로 추가하지 않습니다.

⑫ qu가 비었으므로 종료합니다.

⑬ 이 과정으로 출력된 꼭짓점 순서는 1 → 2 → 3 → 4 → 5입니다.