그래프 탐색(DFS&BFS)

그래프 탐색  개요

---

DFS,BFS 모두 그래프를 탐색하는 방법이다.

그래프 탐색 : 하나의 정점으로부터 시작하여 모든 정점들을 한 번씩 방문하는 것

DFS

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
  
  • 형제 정점을 탐색하기 전에 자식 정점부터 탐색
• 모든 노드를 방문하고자 하는 경우 사용한다.(완전탐색)
• 예) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 방식
• 구현 : 스택 또는 재귀 함수로 구현
  • *참고로 재귀 함수는 내부 스택이 구현되어있음

BFS

• root 노트에서 시작하여 인접한 노드를 먼저 탐색하는 방법으로 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법
• 구현 : 큐를 이용해서 구현

 

 

DFS

---

탐색 순서

(전위 순회와 유사)

1. 하나의 정점에서 시작
2. 간선을 따라 다음 정점으로 방문
3. 더 이상 탐색할 간선이 없으면 역추적(backtracking)을 통해 이전 정점으로 이동하면서 탐색하지 않은 간선이 있는지 확인
4. 탐색 가능한 간선이 있다면 다시 간선을 따라 다음 정점으로 이동
5. 모든 정점을 탐색할 때까지 3,4를 반복
   
   

 

탐색 과정

1. 시작 정점을 스택에 push
2. 스택에 맨 위에 있는 정점을 pop 하고 방문 표시
3. pop 된 정점에서 방문하지 않은 인접한 정점들을 스택에 push
4. 스택이 빌 때까지 2번 3번을 반복

 

 

구현 코드

• 재귀를 사용한 구현

public class Study_DFS_Recursion {
 
	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void main(String[] args) {
		DFS(1);
	}
	
	static void DFS(int nodeIndex) {
		// 방문 처리
		vistied[nodeIndex] = true;
		
		// 방문 노드 출력
		System.out.print(nodeIndex + " -> ");
		
		// 방문한 노드에 인접한 노드 찾기
		for (int node : graph[nodeIndex]) {
			// 인접한 노드가 방문한 적이 없다면 DFS 수행
			if(!vistied[node]) {
				DFS(node);
			}
		}
	}
}

 

• stack을 사용한 구현

import java.util.Stack;
 
public class Study_DFS_stack {
 
	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	// DFS 사용 할 스택
	static Stack<Integer> stack = new Stack<>();
	
	public static void main(String[] args) {
		
		// 시작 노드를 스택에 넣어줍니다.
		stack.push(1);
		// 시작 노드 방문처리
		vistied[1] = true;
		
		// 스택이 비어있지 않으면 계속 반복
		while(!stack.isEmpty()) {
			
			// 스택에서 하나를 꺼냅니다.
			int nodeIndex = stack.pop();
			
			// 방문 노드 출력
			System.out.print(nodeIndex + " -> ");
			
			// 꺼낸 노드와 인접한 노드 찾기
			for (int LinkedNode : graph[nodeIndex]) {
				// 인접한 노드를 방문하지 않았을 경우에 스택에 넣고 방문처리 
				if(!vistied[LinkedNode]) {
					stack.push(LinkedNode);
					vistied[LinkedNode] = true;
				}
			}
		}
	}
}

 

BFS

---

탐색 순서

(레벨 순회로 진행)

1. 처음에 레벨 0에 있는 한 정점에서 시작
2. 먼저 레벨 1의 모든 정점들을 방문 (시작 정점에서 거리가 1인 정점들)
3. 그다음 레벨 2의 모든 정점들을 방문 (시작 정점에서 거리가 2인 정점들)
4. 레벨을 ++하면서 모든 레벨에 있는 노드들을 방문할 때까지 반복
   
   

 

탐색 과정

1. 모든 정점을 방문하지 않은 상태로 표시
2. 시작 정점을 방문하여 방문 표시를 한 뒤 큐에 삽입
3. 큐에서 첫 번째 정점을 제거하고 제거된 정점에서 방문하지 않은 인접한 정점을 방문하여 방문 표시를 한 뒤 큐에 삽입
4. 인접한 정점이 없는 경우 큐에서 첫 번째 정점을 빼옴
5. 큐가 빌 때까지 3번 4번을 반복

 

 

 

 

구현 코드

import java.util.LinkedList;
import java.util.Queue;
 
public class StudyBFS {
	
	public static void main(String[] args) {
		
		// 그래프를 2차원 배열로 표현해줍니다.
		// 배열의 인덱스를 노드와 매칭시켜서 사용하기 위해 인덱스 0은 아무것도 저장하지 않습니다.
		// 1번인덱스는 1번노드를 뜻하고 노드의 배열의 값은 연결된 노드들입니다.
		int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
		
		// 방문처리를 위한 boolean배열 선언
		boolean[] visited = new boolean[9];
		
		System.out.println(bfs(1, graph, visited));
		//출력 내용 : 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7 -> 
	}
	
	static String bfs(int start, int[][] graph, boolean[] visited) {
		// 탐색 순서를 출력하기 위한 용도
		StringBuilder sb = new StringBuilder();
		// BFS에 사용할 큐를 생성해줍니다.
		Queue<Integer> q = new LinkedList<Integer>();
		 
		// 큐에 BFS를 시작 할 노드 번호를 넣어줍니다.
		q.offer(start);
		
		// 시작노드 방문처리
		visited[start] = true;
		
		// 큐가 빌 때까지 반복
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			sb.append(nodeIndex + " -> ");
			//큐에서 꺼낸 노드와 연결된 노드들 체크
			for(int i=0; i<graph[nodeIndex].length; i++) {
				int temp = graph[nodeIndex][i];
				// 방문하지 않았으면 방문처리 후 큐에 넣기
				if(!visited[temp]) {
					visited[temp] = true;
					q.offer(temp);
				}
			}
		}
		// 탐색순서 리턴
		return sb.toString() ;
	}
}

 

 

 

 

 

 

https://yoongrammer.tistory.com/85

[자료구조] 그래프 순회 (Graph traversal) 개념 및 구현