깊이 우선 탐색
-
그래프의 깊이 우선 탐색알고리즘 이론/알고리즘 구현 2019. 8. 25. 02:45
깊이 우선 탐색(DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에, dfs() 만으로는 모든 정점을 순서대로 발견한다는 목적에 부핮하지 않는다. 따라서 dfsAll()을 통해 모든 정점을 방문해야 한다. 코드 ( C++ ) #include #include #include using namespace std; //그래프의 인접 리스트 표현vector adj;// 각 정..