그래프 탐색 알고리즘

그래프 traversal : 그래프의 노드들을 방문하는 과정. search라고도 쓰임.

 

왼쪽이 BFS,  우측이 DFS

breadth-fist search : 너비 우선

depth-first search : 깊이 우선

 

스택. 큐와 연계하여 어떻게 실행할까?

 

 

bfs : 

밑에는 queue array이고 위에는 우리가 정렬하려는 트리.

 

A를 시작 vertex로 큐에 넣는다. 그다음 A를 큐에서 팝 하면서 visit됨을 표현한다. 그다음 큐에 A와 인접한 B, C, E 를 넣는다. B, C, E 는 같은 breath 상이므로 뭘 넣던 상관이 없는것 같다. B를 먼저 팝하고 그와 인접하며 큐에 있지 않는 D를 푸쉬 한다. 그다음은 C를 팝하고 인접한 F를 푸쉬한다. 그다음 E를 팝하고 인접한 H와 G를 푸쉬한다.

 

다음은 D를 팝. F를 팝. H를 팝하면서 I를 푸쉬. G를 팝. 마지막으로 I를 팝한다. 이렇게 큐에 푸쉬하고 팝하면서 나온 리스트는 [A, B, C, E, D, F, H, G, I]가 된다.

 

 

 

 

dfs :

dfs는 bfs와 알고리즘이 같으나, 자료구조가 스택이 된다. 결국 팝된 순서는 [A-E-H-I-G-C-F-D-B] 순서데로 방문된다.

 

 

 

dfs 순서든 bfs 순서든 오직 하나의 것만이 있지는 않다. 왜냐면 A를 팝하며 BCE를 넣는 순서가 달라질수 있기 때문이다.

 

노드간의 connect여부를 dfs, bfs를 활용하여 확인할 수 있다.

 

 

Reference :

http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/e5c9ce8e59584600bc3b095ed2f72fa8/b05b76f4eef04965ad176963d95ba095/?child=first