그래프의 깊이 우선 탐색

깊이 우선 탐색(DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건

따라가는 것. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.

그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에, dfs() 만으로는 모든 정점을 순서대로 발견한다는 목적에 부핮하지 않는다. 따라서 dfsAll()을 통해 모든 정점을 방문해야 한다.

코드 ( C++ )

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

//그래프의 인접 리스트 표현

vector<vector<int>> adj;

// 각 정점을 방문했는지 여부를 나타낸다.

vector<bool> visited;

//깊이 우선 탐색 구현

void dfs(int here) {

cout << "DFS visits " << here << endl;

visited[here] = true;

// 모든 인접 정점을 순회하면서

for (int i = 0; i < adj[here].size(); ++i) {

int there = adj[here][i];

// 아직 방문한 적 없다면 방문한다.

if (!visited[there])

dfs(there);

}

// 더이상 방문할 정점이 없으니 재귀호출 종료 후 이전 정점으로 돌아간다.

}

// 모든 정점을 방문한다.

void dfsAll() {

// visitied 초기화

visited = vector<bool>(adj.size(), false);

// 모든 정점을 순회하면서, 아직 방문한 적 없으명 방문한다.

for (int i = 0; i < adj.size(); ++i)

if (!visited[i])

dfs(i);

}

int main()

{

int n;

cin >> n;

adj = vector<vector<int>>(n, vector<int>());

adj[0].push_back(1);

adj[0].push_back(6);

adj[1].push_back(0);

adj[1].push_back(5);

adj[6].push_back(0);

adj[2].push_back(3);

adj[2].push_back(7);

adj[2].push_back(4);

adj[3].push_back(2);

adj[3].push_back(4);

adj[7].push_back(4);

adj[7].push_back(2);

dfsAll();

}

참고 문헌 : 알고리즘 해결 전략