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

📝그래프 탐색 알고리즘 : DFS/BFS 

• 탐색이란?
  • 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
• 대표적인 그래프 탐색 알고리즘이 바로 DFS와 BFS 
• DFS와 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 공부하자!!!! 

 

📝공부 전 알아야 하는 지식 - 자료구조

스택 

• 먼저 들어온 데이터가 나중에 나가는 형식(Last - In - First - Out)의 자료구조이다.
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있어요! 

import java.util.Stack;
Stack<String> stack = new Stack<>();
stack.push(""); //스택에 데이터를 추가
stack.pop(); //스택에서 데이터를 가져온다. (삭제됨)
stack.peek() //스택 맨 위의 데이터를 확인한다.
stack.isEmpty() //스택이 비어있는지 확인한다.
stack.size() //스택의 사이즈를 확인한다. 

큐

• 먼저 들어 온 데이터가 먼저 나가는 형식(First - In - First - Out)의 자료구조이다.
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.!

import java.util.LinkedList;
import java.util.Queue;
Queue<String> queue =new LinkedList<>();
queue.ofter(""); //큐에 데이터 추가 
queue.peek() //큐의 맨 앞 데이터 확인
queue.poll() //큐에서 데이터를 가져온다. (삭제됨)
queue.isEmpty() //큐가 비어있는지 확인한다.
queue.size() //큐의 사이즈를 확인한다.

 

재귀 함수

• 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 

 

📝DFS 

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 
• DFS는 스택 자료구조를 이용한다.
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
     • 만약 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

재귀 함수 사용 

import java.util.*;

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);
        }
    }
}

스택 사용

import java.util.ArrayList;
import java.util.Stack;

public class Graph {
    public static boolean[] visited = new boolean[9]; // 방문 기록
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static Stack<Integer> stack = new Stack<>();

    // 그래프 초기화 메서드
    public static void initializeGraph(int vertices) {
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
    }

    // 간선 추가 메서드
    public static void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u); // 무방향 그래프인 경우
    }
    // DFS 구현 메서드
    public static void dfs(int start) {
        stack.push(start);

        while (!stack.isEmpty()) {
            int current = stack.pop();

            if (!visited[current]) {
                System.out.print(current + " ");
                visited[current] = true;

                // 현재 정점과 연결된 인접 정점들을 스택에 추가
                for (int i = graph.get(current).size() - 1; i >= 0; i--) {
                    int neighbor = graph.get(current).get(i);
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        initializeGraph(5);
        // 간선 추가
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(2, 4);

        System.out.println("DFS 결과:");
        dfs(0);
    }
}

DFS는 경로문제, 위상정렬 문제에 효과적이다.

📝BFS

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.
  1.  탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  2.  큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 

    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드를 방문 처리
        visited[start] = true;
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            System.out.print(x + " ");
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if(!visited[y]) {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

 

BFS는 최단 경로 탐색, 최소 생성 트리, 레벨 순회에 유용하다.