알고리즘/개념
DFS와 DFS
빵파레2
2019. 9. 10. 14:31
DFS와 BFS란?
- DFS와 BFS는 모두 그래프를 탐색하는 알고리즘이다.
- 두 탐색은 모든 정점을 한번씩 방문한다는 동일한 목표를 가지고 있지만, 그 과정에서 탐색하는 방식에는 차이가 있다.
- DFS는 위의 그림과 같이 해당 노드를 기준으로 더 깊은 노드를 우선적으로 탐색하는 방식이다. (스택을 사용하여 구현하지만 스택을 사용하지 않고도 구현 가능하다는 특징을 가짐, 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문)
- BFS는 너비를 우선적으로 탐색하는 방식이다. (최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용함)
| DFS | BFS |
| 인접행렬 혹은 인접리스트로 그래프 구현 | 인접행렬 혹은 인접리스트로 그래프 구현 |
| 스택 혹은 재귀로 구현 | 큐로 구현 |
DFS 구현
- DFS 또는 BFS를 구현하기에 앞서 먼저 그래프를 구현해야 한다.
- 그래프를 구현하는 방법으로는 인접행렬, 인접리스트로 구현하는 방법이 있다.
- 그래프의 정점의 개수를 V, 간선의 개수를 E 라고 가정했을때, 인접행렬은 시간복잡도가 O(V^2) 이고 인접리스트는 시간복잡도가 O(V+E) 이다.
- 따라서 정점과 간선의 개수가 많아지면 인접리스트가 성능면에서 유리할 수 있다.
- DFS는 스택으로 구현하거나 재귀를 이용해 구현할 수 있다.
1. 인접행렬, 스택을 이용해 구현한 DFS
public class DFS {
// 정점 개수
static int n = 9;
// 간선 개수
static int e = 8;
// 인접행렬
static int[][] a = new int[n+1][n+1];
// checker
static boolean[] checker = new boolean[n+1];
// flag
static boolean flag;
static void dfs(int[][] a, boolean[] c, int v) {
// 스택
Stack<Integer> stack = new Stack<>();
System.out.print(stack.push(v) + " ");
c[v] = true;
while(!stack.isEmpty()) {
int top = stack.peek();
flag = false;
for (int i = 1; i <= n; i++) {
if (a[top][i] == 1 && !c[i]) {
stack.push(i);
System.out.print(i + " ");
c[i] = true;
flag = true;
break;
}
}
if (!flag) {
stack.pop();
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 인접행렬 만들기
for (int i = 0; i < e; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
a[v1][v2] = 1;
a[v2][v1] = 1;
}
dfs(a, checker, 1);
}
}
2. 인접리스트, 재귀를 이용해 구현한 DFS
public class DFS {
// 정점 개수
static int n = 9;
// 간선 개수
static int e = 8;
// 인접리스트
static ArrayList<Integer>[] al = (ArrayList<Integer>[]) new ArrayList[n+1];
// checker
static boolean[] checker = new boolean[n+1];
private static void alDfs(ArrayList<Integer>[] al, boolean[] c, int v) {
// 재귀
c[v] = true;
System.out.print(v + " ");
for (Integer vv : al[v]) {
if (!c[vv])
alDfs(al, c, vv);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 인접리스트 만들기
for (int i = 1; i <= n; i++) {
al[i] = new ArrayList<>();
}
for (int i = 0; i < e; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
al[v1].add(v2);
al[v2].add(v1);
}
alDfs(al, checker, 1);
}
}
BFS 구현
- BFS는 큐를 이용하여 구현할 수 있다.
1. 인접행렬, 큐를 이용해 구현한 BFS
public class BFS {
static int n = 6; // 정점의 수
static int e = 8; // 간선의 수
// 인접 행렬, 무방향 그래프
static int[][] a = new int[n + 1][n + 1];
// checker
static boolean[] c = new boolean[n + 1];
// 인접행렬, checker, 시작정점
static void bfs(int[][] a, boolean[] c, int v) {
Queue<Integer> queue = new LinkedList<>();
int n = a.length - 1;
queue.add(v);
c[v] = true;
while (!queue.isEmpty()) {
v = queue.poll();
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (a[v][i] == 1 && !c[i]) {
queue.add(i);
c[i] = true;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int v1, v2;
// 인접 행렬
for (int i = 0; i < e; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
a[v1][v2] = 1;
a[v2][v1] = 1;
}
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < n+1; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
bfs(a, c, 1);
}
}
2. 인접리스트, 큐를 이용해 구현한 BFS
public class BFS {
// 정점 개수
private static int N;
// 간선 개수
private static int M;
// 시작 정점
private static int V;
// bfs 구현 메서드
private static void bfs(ArrayList<Integer>[] al, boolean[] c, int v) {
Queue<Integer> queue = new LinkedList<>();
queue.add(v);
c[v] = true;
while (!queue.isEmpty()) {
v = queue.poll();
System.out.print(v + " ");
for (Integer i : al[v]) {
if (!c[i]) {
queue.add(i);
c[i] = true;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
// 인접 리스트 (ArrayList의 배열)
ArrayList<Integer>[] al = (ArrayList<Integer>[]) new ArrayList[N+1];
for (int i = 1; i < N+1; i++) {
al[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
al[v1].add(v2);
al[v2].add(v1);
}
// checker
boolean[] checker = new boolean[N+1];
bfs(al, checker, V);
}
}
참고자료