DFS

Depth First Search

stack을 이용하여 갈 수 있는 만큼 최대한 간다. 갈 수 없으면 이전 정점으로 돌아간다.

수행 과정

• 스택을 이용해서 갈 수 있는 만큼 최대한 많이 간다

• 갈 수 없으면 이전 정점으로 돌아간다.

장점

• 현 경로의 노드만 기억하면 되니까 저장 공간의 수요가 다소 적다.

• 목표 노드가 깊은 단계에 있을 경우 빨리 목표점을 찾을 수 있다.

단점

• 해가 없는 경로에 깊이 빠질 수 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지 탐색하고 목표 노드 발견 못하면 다음 경로 탐색하는 방법이 유용할 수 있다.

• 얻어진 해가 최단 경로가 된다는 보장이 없다.

다익스트라 출발점과 도착점 사이의 최단경로 문제를 푸는 알고리즘이다. 단, 조건은

• 어떤 변도 음수 가중치를 갖지 않는다.

• 유향그래프이다.

  예를 들어 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타낸다고 하자.

  변들이 도시 사이를 이동하는 가중치를 나타낸다면, 다익스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.

구현

DFS로 방문한 정점을 순서대로 출력해보자.

1. 그래프를 (from, to) / (to, from)으로 초기화한다.

2. DFS(출발점) 시작한다.

   • 이 때 만약 모든 정점을 탐색해야 한다면, 반복문을 통해 모든 정점을 시작점으로 하여 DFS한다. (방문한 정점을 제외하고.. 탐색된 경로를 또 탐색하여 불필요한 메모리 소비 하지 말자.)

3. DFS를 호출한 정점은 방문한 것으로 체크하고 출력한다.

4. 호출한 정점과 연결된 간선 수 만큼 DFS를 반복한다.

   • 이 때, 방문하지 않은 정점만 DFS 시작한다.

5. 더 이상 연결된 간선의 수가 없는 정점을 stack에 푸쉬한다.

(6. 2~5번 종료시, stack의 값을 꺼내서 값을 출력한다.)

vector <int> graph[1001];
bool isVisited[1001];
int N, M;

void DFS(int start){
    isVisited[start] = true;
    // for문 안에서 방문한 곳은 DFS하지 않는다.
    // 그래서 DFS할 때마다 출력하면, 방문한 정점을 순서대로 출력할 수 있다.
    printf("%d ", start);

    for(int i=0; i< graph[start].size(); i++){
        int to = graph[start][i];
        if(!isVisited[to]){
            DFS(to);
        }
    }
    stack.push(start);
}

int main(){

    int from, to;

    for (int i = 0; i<M; i++){
        scanf("%d %d", &from, &to);
        graph[from].push_back(to);
    }

    // 연결되지 않은 vertex가 있으면 DFS로 갈 수 없기 떄문에..
    for (int i=1; i<=N; i++){
        // DFS로 이미 방문한 곳을 또 DFS할 필요가 없다.
        if (!isVisited[i]){
            DFS(i);
        }
    }
}

Issue

• 그래프에 대한 DFS, BFS든 특별한 말이 없으면 그래프는 양방향이다.

• 그래프에서 DFS 할 경우 갈 때마다 방문 체크하고, 방문 출력한다.

  • 애초에 방문체크하여 DFS하기 때문에 방문할 때마다 방문 출력하자.

참조

위키피디아 DFS