그래프 탐색 - DFS & BFS

# DFS (깊이 우선 탐색)

루트, 혹은 임의 노드까지 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 알고리즘이다.

 

자기자신을 호출하는 순환 알고리즘의 형태로써 스택이나 재귀함수로 구현한다.

 

그래프의 모든 경로를 방문해야할 경우에 사용에 적합하다,

 

# DFS Code

// i 정점부터 시작.
    public static void dfs(int i) {
		visit[i] = true; // 이미 방문한 노드인지 체크를 위한 배열, Boolean
		System.out.print(i + " ");
		
        // j는 dfs 배열의 새로운 브랜치를 뜻함.
        // map은 그래프를 나타내며 그래프 연결 정보를
        // map[a][b] = map[b][a] = 1; 로 저장한다. (a노드와 b노드가 연결되어있다(1)는 정보)
		for(int j=1; j<n+1; j++) {  
			if(map[i][j] == 1 && !visit[j]) {
				dfs(j); // 재귀호출
			}
		}
	}

 

---

# BFS (너비 우선 탐색)

루트, 혹은 임의 노드에서 인접한 노드부터 먼저 탐색하는 알고리즘이다.

 

DFS와 다르게 재귀적으로 동작하지 않는다. 선입선출을 원칙으로 탐색하기 때문에

 

방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐를 통해 구현한다.

 

모든 곳을 탐색하기 보다 최소비용(최단 경로, 임의의 경로) 이 우선일 때 적합한 알고리즘이다.

 

# BFS Code

// i 정점부터 시작.
	public static void bfs(int i) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(i); // 큐에 현재 노드 저장
		visit[i] = true; // 중복 접근 방지를 위한 방문 체크 배열, Boolean
		
		while(!q.isEmpty()) {
			int temp = q.poll(); // 큐에서 우선순위가 제일 높은 노드 꺼냄
			System.out.print(temp + " ");
			for(int j=1; j<n+1; j++) {
				if(map[temp][j] == 1 && !visit[j]) { // 현재 노드와 연결되어있고(1) 미 방문이면
					q.offer(j); // 해당 노드를 큐에 저장
					visit[j] = true;
				}
			}
		}
	}