[Graph] Graph 탐색

그래프 탐색(순회)

• 그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것을 의미→ 깊이 우선 탐색 (Depth First Search, DFS)
• → 너비 우선 탐색 (Breadth First Search, BFS)

너비 우선 탐색(BFS)

• 너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료규조인 큐를 사용

BFS(G, v) // 그래프 G, 탐색 시작 정점 v
	큐 생성
	시작 정점 v를 큐에 삽입
	정점 v를 방문한 것으로 표시
	while(큐가 비어있지 않은 경우){
		t = 큐의 첫 원소 poll()
		for(t와 연결된 모든 간선 탐색){
			u = t의 인접 정점
			u가 방문되지 않은 곳이라면,
			u를 큐에 넣고, 방문한 것으로 표시
		}
	}
end BFS()

private static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean visited[] = new boolean[N];
		
		queue.offer(start); //처음에 0부터 시작
		visited[start] = true; 	// 들어갈때 방문 처리 !!!

		while (!queue.isEmpty()) {			
			int v = queue.poll();		
			System.out.println(v);
			//visited[v] = true; 
			
			for (int i = 0; i < N; ++i) {
				if (map[v][i] && !visited[i]) {
					queue.offer(i);
					visited[i] = true; 	//들어갈때 방문 처리!!!
				}
			}
		}
	}

 

깊이 우선 탐색(DFS)

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택 사용
• → 재귀의 경우도 스택의 자료구조를 사용하기 때문에 사용가능!

DFS(v) // v : 탐색 정점 G : 그래프 visited[v] = true for(v에서 인접한 노드 w){ IF visite

DFS(v) // v : 탐색 정점 G :  그래프
	visited[v] = true

	for(v에서 인접한 노드 w){
		IF visited[w] != TRUE
		DFS(w)
	}
end DFS()

private static void dfs(int v) {// 번호 v로부터 시작하는 dfs
		visited[v] = true;		
		System.out.println(v);

		for (int i = 0; i < N; ++i) { 
			//v번째 행에서 탐색
			if (map[v][i] == true && !visited[i]) {
				//System.out.println(v + ":" + i);
				dfs(i);
			}
		}
	}