그래프 탐색

---

• 그래프 탐색은 비선형구조인 그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것

종류

• 깊이 우선 탐색(Depth Frist Search, DFS)
• 너비 우선 탐색(Breadth First Search, BFS)

DFS (깊이 우선 탐색)

---

• 시작 정점을 시작으로 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
• 더이상 갈 곳이 없다면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아가 같은 방식으로 다시 탐색
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출(LIFO) 구조의 스택 사용
• 시간 복잡도
  • (N: 정점의 수, E: 간선의 수)
  • 인접 리스트 구현: O(N+E)
  • 인접 행렬 구현: O(N^2)

DFS 알고리즘 - 재귀

static int N = 5;
static int[][] matrix = new int[N][N];
static boolean[] visited = new boolean[N];

static void dfs(int node) {
	visited[node] = true; // 방문 체크
	
	for(int next = 0; next < N; next++) {
    	// 방문 했거나, 간선이 없으면 다음으로 넘어감
		if(visited[next] || matrix[node][next] == 0) 
			continue;
		dfs(next);
	}
}

DFS 알고리즘 - 반복문 (스택 이용)

• input 사이즈가 클 경우 이용
• stack을 이용하면 시작 정점과 먼 정점 먼저 확인

static int N = 5;
static int[][] matrix = new int[N][N];

static void dfs(int node) {
	boolean[] visited = new boolean[N];
	Stack<Integer> st = new Stack<>();
	st.push(node); // 시작 정점
	
	while(!st.isEmpty()) {
		int cur = st.pop();
		if(visited[cur]) continue; // 방문 체크
		
		visited[cur] = true; // 안했다면 방문
		
		for(int next = 0; next < N; next++) {
        	// 방문 했거나, 간선이 없으면 다음으로 넘어감
			if(visited[next] || matrix[node][next] == 0) 
				continue;
			st.push(next);
		}
		
	}
	
}

BFS (너비 우선 탐색)

---

• 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문
• 시작점의 인접 정점을 다시 시작점으로 다시 인접한 정점들 차례로 방문
• 인접한 정점들에 대해 탐색한 후, 차례로 다시 너비 우선 탐색 진행해야 하므로 선입선출(FIFO) 형태의 자료구조인 큐 이용
• 가중치가 없는 그래프에서 BFS로 최단 경로 구하기 가능
• 시간 복잡도
  • (N: 정점의 수, E: 간선의 수)
  • 인접 리스트 구현: O(N+E)
  • 인접 행렬 구현: O(N^2)

BFS 알고리즘

static int N = 5;
static int[][] matrix = new int[N][N];

static void dfs(int node) {
	boolean[] visited = new boolean[N];
	Queue<Integer> q = new LinkedList<>();
	q.offer(node);
	
	while(!q.isEmpty()) {
		int cur = q.poll();
		
		for(int next = 0; next < N; next++) {
			if(visited[next] || matrix[node][next] == 0) 
				continue;
			// 중복되서 들어가는 경우 막기 위해
			// 큐 삽입 시 방문 처리
			visited[cur] = true; 
			q.offer(next);
		}
		
	}
	
}