[자료구조 그래프] Search of Graph / 그래프의 탐색

그래프의 탐색에 대해 알아보자

 

깊이 우선 탐색(Depth First Search : DFS)

    - 그래프에는 여러 갈래의 길이 있는데, 한 길을 깊이 파고드는 것

 

출처) 윤성우의 열혈 자료구조

    - 한 사람에게만 연락을 한다

    - 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알린다

    - 처음 연락을 시작한 사람의 위치에서 연락을 끝이 난다

 

깊이 우선 탐색(Depth First Search : DFS) 구현

    - 스택 : 경로 정보의 추적을 목적으로 한다

        - 방문 경로를 push 하여 기록하고 이미 방문한 정점 밖에 없을 경우 뒤로 돌아간다(pop)

    - 배열 : 방문 정보의 기록을 목적으로 한다

        - 정점의 방문 여부를 기록

 

너비 우선 탐색(Breadth First Search : BFS)

    - 연결된 모든 정점에 연락을 취하는 방식

 

너비 우선 탐색(Breadth First Search : BFS) 구현

    - 큐 : 방문 차례의 기록을 목적으로 한다

        - 방문 당한 정점을 큐에 기록(enqueue)한 후

          방문 당한 정점을 기준(dequeue)으로 다시 방문되지 않은 정점을 방문한다

    - 배열 : 방문 정보의 기록을 목적으로 한다

        - 정점의 방문 여부를 기록