[알고리즘] DFS & BFS : 그래프 탐색

사전지식

• 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

스택 자료구조
: 선입후출 ( 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조 )

큐 자료구조
: 선입선출 (먼저 들어온 데이터가 먼저 나가는 형식의 자료구조)

재귀함수 (Recursive Function )

• 자기 자신을 다시 호출하는 함수
• 문제풀이에서 사용할 때는 종료조건을 반드시 명시해야 함
• 종료조건을 명시하지 않으면 무한이 호출 될 수 있음
• 모든 재귀함수는 반복문으로 구현 가능
• 재귀함수가 반복문보다 불리한 경우도 있고 유리한 경우도 있음
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임
  -> 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀를 이용

DFS (Depth-First Search)

• 깊이 우선 탐색, 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조나 재귀함수를 이용

구체적인 동작과정
1. 탐색 시작 노드를 스택에 삽입하고 방문처리 합니다.
2. 스택 최상단노드에 방문하지 않는 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 합니다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

Public Class Main {
	public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    
    public static void dfs(int x) {
    	visited[x] = true;
        
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for(int i = 0; i<graph.get(x).size(); i++) {
        	int y = graph.get(x).get(i);
            if(!visited[y]) dfs(y);
        }
    }
    
    public static void main(String[] args) {
    	dfs(1);
    }
}

BFS

참고

• https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2069s