DFS(깊이우선탐색)

[광고 누르면 오늘의 행운 상승!!]

• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를
  빠짐없이 검색하는 것이 중요함.
  
  
• 두가지 방법
  - 깊이 우선 탐색(Depth First Search)
  - 너비 우선 탐색(Breadth First Search)
  
  
• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가
  더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는
  정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든
  정점을 방문하는 순회방법
  
  
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을
  반복해야 하므로 후입선출 구조의 스택 사용

DFS(재귀를 이용한 방법)

package DFS;

import java.io.*;
import java.util.*;
public class DfsTest {

	public static int V,E;
	public static int[][] graph;
	public static boolean[] visit;
	public static Stack<Integer> stack;
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_dfs.txt"));
		Scanner sc=  new Scanner(System.in);

		V = sc.nextInt();
		E = sc.nextInt();
		
		graph = new int[V][V];
		
		for(int i =0; i < E ; i++) {
			int v = sc.nextInt();
			int u = sc.nextInt();
			graph[v][u] = graph[u][v] =  1;
			
		}
		//for(int[] a: graph) System.out.println(Arrays.toString(a));
		
		visit = new boolean[V];
		dfs(0);
		sc.close();
	}
	public static void dfs(int node) {
		visit[node] = true;
		System.out.print(node + " ");
		
		for (int next = 0; next < V; next++) {
			if(!visit[next] && graph[node][next] == 1) { //방문하지 않았고 인접하여 있다면.
				dfs(next);
			}
		}
	}

}

DFS(스택을 이용한 방법)

package DFS;

import java.io.FileInputStream;
import java.util.Scanner;
import java.util.Stack;

public class DfsTest2 {

	public static int V,E;
	public static int[][] graph;
	public static boolean[] visit;
	public static Stack<Integer> stack;
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_dfs.txt"));
		Scanner sc=  new Scanner(System.in);

		V = sc.nextInt();
		E = sc.nextInt();
		
		graph = new int[V][V];
		stack = new Stack<Integer>();
		
		for(int i =0; i < E ; i++) {
			int v = sc.nextInt();
			int u = sc.nextInt();
			graph[v][u] = graph[u][v] =  1;
			
		}
		//for(int[] a: graph) System.out.println(Arrays.toString(a));
		
		visit = new boolean[V];
		dfs2(0);
		sc.close();
	}
	public static void dfs2(int node) {
		visit = new boolean[V];
		stack.push(node);
		while(!stack.empty()) {	
			int curr = stack.pop();
			if(!visit[curr]) { //방문하지 않았다.
				visit[curr] = true;
				System.out.print(curr + " ");
				for(int next = V-1; next>=0; next--) { // 0 1 3 5 4 2 6 //왼쪽부터
				//for (int next = 0; next < V; next++) { // 0 2 4 5 6 3 1 //오른쪽부터
					if(!visit[next] && graph[curr][next] == 1) {
						stack.push(next);
					}
				}
			}
		}
	}
	
	
}