깊이 우선 탐색
깊이 우선 탐색 개념
- 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
- 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 탐색
- 해당 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.
- 모든 노드를 방문하고자 하는 경우에 선택
- 깊이 우선 탐색(DFS)가 너비 우선 탐색(BFS)보다 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.
깊이 우선 탐색(DFS)의 특징
- 순환 알고리즘의 형태를 갖고 있다.
- 전위 순회(Pre-Order)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
- 그래프 탐색할 때 어떤 노드를 방문했었는지 여부를 반드시 검사한다.
코드 설계
- 시작 노드(1)로부터 인접 노드(2, 3)를 모두 방문
- 인접 노드(2, 3)를 스택에 넣고 방문처리
- 시작 노드(1)로부터 인접한 노드 중에 방문하지 않은 노드가 더이상 없는 경우
- 이전의 위치로 돌아와 찾아가지 않은 다른 길로 탐색한다.
코드 구현
- 순환 호출을 이용한 DFS 구현
public class DFSList {
static class Graph {
private int V;
private LinkedList<Integer>[] adjacent;
@SuppressWarnings("unchecked")
public Graph(int V) {
this.V = V;
this.adjacent = new LinkedList[V];
for (int i = 0; i < V; i++) adjacent[i] = new LinkedList<>();
}
public void addEdge(Graph graph, int src, int dest) {
graph.adjacent[src].add(dest);
graph.adjacent[dest].add(src);
}
public void printGraph(Graph graph) {
for (int v = 1; v < graph.V; v++) {
System.out.println("Node [" + v + "]");
System.out.print("adjacent Node: ");
for (Integer node : graph.adjacent[v]) {
System.out.print("[" + node + "]\t");
}
System.out.println();
}
}
/**
* 비연결형 그래프의 경우, 모든 정점을 하나씩 방문하는 너비 우선 탐색
* @param start
*/
public void dfs() {
boolean[] visit = new boolean[V];
for(int i = 1 ; i < V ; i++) {
if(visit[i] == false)
dfsUtil(i, visit);
System.out.println();
}
}
/**
* 주어진 노드를 시작한 너비 우선 탐색
* @param start
*/
public void dfs(int start) {
boolean[] visit = new boolean[V];
dfsUtil(start, visit);
System.out.println();
}
/**
* 인접한 노드 방문 하는 DFS 재귀함수
* @param start
* @param visit
*/
private void dfsUtil(int start, boolean[] visit) {
visit[start] = true; // 방문 체크
System.out.print(start + "\t");
Iterator<Integer> it = adjacent[start].listIterator(); // 인접한 노드 리스트
while(it.hasNext()) {
int n = it.next();
if(!visit[n]) // 방문 확인 false인 경우, 노드 탐색
dfsUtil(n, visit);
}
}
}
public static void main(String[] args) {
int initSize = 8;
Graph graph = new Graph(initSize);
graph.addEdge(graph, 1, 2);
graph.addEdge(graph, 1, 3);
graph.addEdge(graph, 2, 3);
graph.addEdge(graph, 2, 4);
graph.addEdge(graph, 2, 5);
graph.addEdge(graph, 3, 6);
graph.addEdge(graph, 3, 7);
graph.addEdge(graph, 4, 5);
graph.addEdge(graph, 6, 7);
graph.printGraph(graph);
graph.dfs(4); /* 주어진 노드를 기준으로 BFS 탐색 */
graph.dfs();
}
}- Graph의 각 노드에 연결된 노드 리스트 및 DFS 결과
// 노드별 연결 리스트 확인
Node [1]
adjacent Node: [2] [3]
Node [2]
adjacent Node: [1] [3] [4] [5]
Node [3]
adjacent Node: [1] [2] [6] [7]
Node [4]
adjacent Node: [2] [5]
Node [5]
adjacent Node: [2] [4]
Node [6]
adjacent Node: [3] [7]
Node [7]
adjacent Node: [3] [6]
// 주어진 노드를 기준으로 DFS 탐색
4 2 1 3 6 7 5
// 모든 노드 탐색
1 2 3 6 7 4 5 분석
- 깊이 우선 탐색(DFS)의 시간 복잡도
- 인접 리스트로 표현된 그래프: O(N+E)
- 인접 행렬로 표현된 그래프: O(N^2)
'알고리즘&자료구조 > basic' 카테고리의 다른 글
| [알고리즘] 너비 우선 탐색(Breadth First Search, BFS) (0) | 2020.05.13 |
|---|---|
| [자료구조] 그래프(Graph) (0) | 2020.05.13 |
| [자료구조] 트리(Tree) (0) | 2020.05.12 |
| [자료구조] 큐(Queue) (0) | 2020.05.12 |
| [자료구조] 스택(Stack) (0) | 2020.05.10 |