오늘은 깊이 우선 탐색을 알아보려 합니다.

그래프 순회

그래프의 순회란 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것을 말합니다.

그래프의 탐색 방식에는 깊이 우선 탐색과 너비 우선 탐색이 있습니다만, 오늘은 깊이 우선 탐색을 알아보고자 합니다.

dfs

깊이 우선 탐색은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없다면 가장 마지막에 만난 갈림길에서 안 간 길의 정점에서 다시 다른 방향으로 전진합니다.

가장 마지막에 만난 갈림길에서 다시 다른 방향으로 전진하는 방식을 반복하기 위해서는 후입선출 구조의 스택을 사용합니다.

순서

1. 시작 정점 v 결정하고 방문

2. 정점 v에 인접한 정점중에서 방문하지 않은 정점이 있으면 v를 스택에 넣고 방문하지 않는 정점을 방문

3. 방문하지 않은 정점을 v로 설절하고 다시 2번째를 반복

4. 방문하지 않은 정점이 없다면 스택에서 빼내어 구한 가장 마지막 방문 정점을 v로 설정하고 다시 2번째를 반복

5. 스택이 공백될 때까지 2번째를 반복

의사 코드

for(i<-0;i<n;i-<i+1)do{
    visit[i] <- false;
}
stack<-create();
visit[v]<-true;
v<-visited;
while(not isEmpty()){
    if(visit[w] = false)then{
        push(stack, v);
        visitp[w]<-true;
        w<-visited;
        v<-w;
    }
    else{
        v<-pop(stack);
    }
}