그래프와 DFS & BFS

DFS와 BFS는 그래프를 완전탐색하는 기법 중 하나이다. DFS와 BFS를 이해하고 코드를 구현하기 위해 그래프부터 이해해보자!

그래프 표현 방법

---

DFS (깊이 우선 탐색)

DFS는 한 노드에 관해 해당 노드에 연결되어 있는 노드를 끝까지 탐색한 후 다음 노드로 넘어간다.

O(V+E)의 시간복잡도를 가지고 있다. (V: node 갯수, E: edge 갯수)

DFS는 재귀함수 호출 또는 스택을 이용하여 구현할 수 있다.
(재귀를 사용한다는게 메모리의 스택구조를 이용한다는 점에서 코드의 기반이 크게 다르지 않다.)

한번 방문한 노드는 다시 방문할 필요가 없으므로 배열을 통해 방문 여부를 체크해야한다.

노드 방문 순서는 스택 삽입순서이며 시작노드나 구현에 따라 순서는 다르다.

DFS 과정(1) 스택

1. 인접리스트를 통해 그래프를 표현한다.
   ArrayList<노드 데이터의 자료형>[노드갯수]

2. 방문배열 초기화
   visited[노드갯수] 배열을 생성해준다.

3. 시작 노드 스택에 넣어주기
   노드를 탐색하기 위해 스택에 시작 노드 하나를 넣어준다.
   해당 노드에 대한 visited 값을 true로 바꿔준다.

4. 스택에 있는 노드 꺼내기 stack.pop()

5. 스택에서 꺼낸 노드에 대한 인접노드 중 방문배열 값이 false인 노드를 스택에 모두 넣어준다. stack.push()

6. 스택에 넣은 노드에 대한 방문배열 값을 true로 바꿔준다.

7. 스택에 값이 없을 때까지 4~6의 과정을 반복한다.

import java.util.ArrayList;

public class Main {
	static boolean[] visited;
	static ArrayList<Integer>[] graph;
	public static void main(String args[]){
		int V = 6;
		int E = 6;
		int[][] nodes = {{1,2}, {1,3}, {2, 5}, {2, 6}, {3,4}, {4,6}};
		visited = new boolean[V+1];
		graph = new ArrayList[V+1];
		for (int i = 0; i <= V; i++) {
			graph[i] = new ArrayList<>();
		}
		// 그래프 표현
		for (int i=0; i<nodes.length; i++){
			graph[nodes[i][0]].add(nodes[i][1]);
		}
			dfs(V, E, nodes);
	}
    static void dfs(int V, int E, int[][]nodes) {
		// 스택에 탐색 시작 노드 삽입
		Stack stack = new Stack();
		stack.push(1);
		visited[0] = true;
		visited[1] = true;

		// 탐색
		while(!stack.isEmpty()){
			int node = (int)stack.pop();
			for (int i=0; i<graph[node].size(); i++){
				int target = graph[node].get(i);
				if(visited[target] == false){
					stack.push(target);
					visited[target] = true;
				}

			}
		}
	}
}

DFS 과정 (2) 재귀

import java.util.ArrayList;

public class Main {
	static boolean[] visited;
	static ArrayList<Integer>[] graph;
	public static void main(String args[]){
    
		... 초기세팅 ...
        
		dfs(1);

	}
	static void dfs(int start){
		if(!visited[start]) visited[start] = true;
		else return;
		System.out.println(start);
		for(int i=0; i<graph[start].size(); i++){
			int y = (int)graph[start].get(i);
			if(visited[y] == false)
				dfs(y);
		}
	}
}

실행순서 1-2-5-6-3-4

BFS (너비우선탐색)

• 탐색 시작 노드의 가까운 노드를 우선하여 탐색하기 때문에 목표노드의 최단 경로를 보장한다.
• Queue 자료구조를 사용하며 FIFO 방식에 따라 진행된다.
• 시간복잡도 O(V+E)

과정

1. DFS와 동일하게 그래프를 인접리스트로 표현해준다.
2. 방문배열을 초기화해준다.
3. 시작노드를 큐에 넣어준다.
4. 큐에 들어간 노드의 방문 배열값을 true로 바꿔준다.
5. 큐에 있는 노드를 빼며, 해당 노드의 인접 노드를 큐에 넣어준다.
6. 4-5 과정을 큐가 빌 때까지 반복한다.

방문순서: 1-2-5-4-6-5

public class Main {
	static ArrayList<Integer>[] graph;
	static boolean[] isVisited;

	public static void main(String args[]){
    
		... 그래프 구현 ...
        
		BFS(V);
	}
	public static void BFS(int start){
		Queue<Integer> queue = new LinkedList<>();

		queue.add(start);
		isVisited[start] = true;

		while (!queue.isEmpty()){
			int node = queue.poll();
			System.out.print(node+ " ");
			for (int i=0; i<graph[node].size(); i++){
				int next = graph[node].get(i);
				if(!isVisited[next]) {
					queue.add(next);
					isVisited[next] = true;
				}
			}
		}
	}
}

---

🙇🏻‍♀️ 참고
Do it! 알고리즘 코딩 테스트 자바 편