[C++] 파일 입출력 - dfs [2]

저번 글에 이어 이번 글에서는 그래프를 읽어온 결과를 바탕으로 그래프 상에서 dfs를 해보겠다.

---

0. 그래프 구조

먼저, 저번 글에서 사용한 그래프 구조를 직접 그리면 다음과 같다.

1. dfs 코드

dfs는 Depth-First-Search의 약자로 현재 정점에서 다음 정점으로 갈 수 있는 경우, 탐색을 계속하며 다음 정점이 없는 경우에는 부모 정점으로 돌아가 다시 갈 수 있는 정점가 있는지 판단한다.

다음 정점이 있는 경우 계속해서 탐색을 하기 때문에 트리에서 탐색할 경우, 루트 노드에서 계속해서 높이를 내려가면서 탐색을 하므로 dfs라는 이름이 붙었다.

 

코드 전반은 다음과 같다.

int dfs(vector<vector<int>> &graph, vector<int>& visited, int n){
    cout << "Vertex " << n << "\n";
    visited[n - 1] = 1;

    for(int i = 0; i < graph[n - 1].size(); i++){
        int idx = graph[n - 1][i];
        if(!visited[idx - 1]){
            dfs(graph, visited, idx);
        }
    }
    return 0;
}

그래프 정보를 저장하는 이차원 배열 graph와 방문 여부를 저장하는 배열visited, 현재 정점 번호를 저장하는 idx 변수를 매개변수로 가진다.

 

재귀함수를 이용해 코드를 구현했으며(스택을 이용해도 가능하다) 정점을 방문할 시 현재 정점에 방문처리를 한다.

 

그리고 현재 정점에 연결된 다른 정점들을 방문했는지 체크하며, 만약 방문하지 않았다면 그 정점을 방문한다.

결과는 다음과 같다.

8번 정점에서 5번 정점으로 가는 이유는, 8번 정점에서 5번 정점으로 갈 수 있기 때문이다.

dfs는 높이가 위에서 아래로 내려가는 것만이 아니라, 다음에 갈 수 있는 정점이 있는지 여부를 가지고 탐색을 계속한다.