DFS 와 BFS 개념정리

그래프를 탐색하기 위한 대표적인 알고리즘 - DFS , BFS (이해하려면 스택,큐,재귀함수를 알아야한다)

 

🁢 탐색 Search

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.

 

🁢 자료구조 Data Structure 

데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.

• 삽입(Push) : 데이터를 삽입한다.
• 삭제(Pop) : 데이터를 삭제한다.

🁢 스택(Stack)

박스 쌓기에 비유

선입후출(First In Last Out)

 

▒ java ▒

* 자바에서 스택의 최상단 원소를 출력할때 peek() 메서드사용

import java util.*;
 
public calss Main{
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>();
 
        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        s.push(5);   
        s.push(2);   
        s.push(3);   
        s.push(7);   
        s.pop();
        s.push(1);
        s.push(4);    
        s.pop();
        // 스택의 최상단 원소부터 출력
        while(!s.empty()){
            System.out.print(s.peek() + " ");
            s.pop();
        }
    }
}
          

🁢 큐(Queue)

입구와 출구가 모두 뚫려 있는 터널로 비유

선입선출(First In First Out)

 

▒ java ▒

import java util.*;
 
public calss Main{
    public static void main(String[] args){
        Queue<Integer> q = new LinkedList<>();
 
        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        s.offer(5);   
        s.offer(2);   
        s.offer(3);   
        s.offer(7);   
        s.poll();
        s.offer(1);
        s.offer(4);    
        s.poll();
        // 먼저 들어온 원소부터 출력
        while(!q.empty()){
            System.out.print(q.poll() + " ");
        }
    }
}
          

 

 

🁢 재귀 함수 Recursive Function

자기 자신을 다시 호출하는 함수

재귀 함수를 문제 풀이에서 사용할 시 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.

---

🌀 DFS

- Depth-First-Search , 깊이 우선 탐색 

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

 * 그래프는 노드(Node) 와 간선(Edge) 로 표현되며 이때 노드를 정점(Vertex) 라고도 한다

 * 프로그래밍에서 그래프는 크게 2가지 방식으로 표현

    1. 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

      - 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

    2. 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

      - 연결리스트 자료구조를 이용하여 구현하는데 C++나 자바는 별도로 연결 리스트 기능을 위한 표준 라이브러리를          제공한다

 

DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다

① 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

- DFS 는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개의 경우 O(N) 의 시간이 소요된다는 특징이 있다. 또한 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.

 

▒ DFS.py ▒

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
 
    # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
    graph = [
            [],
            [2,3,8],
            [1,7],
            [1,4,5],
            [3,5],
            [3,4],
            [7],
            [2,6,8],
            [1,7]
            
    ]
 
    # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
    visited = [False] * 9
 
    # 정의된 DFS 함수 호출
    dfs(graph, 1, visited)

▒ dfs.java ▒

 
import java.util.ArrayList;
 
public class dfs {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
 
    // dfs 함수 정의
    public static void dfs(int x){
        // 현재 노들르 방문 처리
        visited[x] = true;
        System.out.println(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        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) {
        // 그래프 초기화
        for(int i=0; i<9; i++){
            graph.add(new ArrayList<Integer>());
        }
        // 노드 1에 연결된 노드 정보 저장
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
 
        // 노드 2에 연결된 노드 정보 저장
        graph.get(2).add(1);
        graph.get(2).add(7);
 
        // 노드 3에 연결된 노드 정보 저장
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
 
        // 노드 4에 연결된 노드 정보 저장
        graph.get(4).add(3);
        graph.get(4).add(5);
 
        // 노드 5에 연결된 노드 정보 저장
        graph.get(5).add(3);
        graph.get(5).add(4);
 
        // 노드 6에 연결된 노드 정보 저장
        graph.get(6).add(7);
 
        // 노드 7에 연결된 노드 정보 저장
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
 
        // 노드 8에 연결된 노드 정보 저장
        graph.get(8).add(1);
        graph.get(8).add(7);
 
        dfs(1);
    }
}

🌀 BFS

- Breadth-First Search , 너비 우선 탐색 

- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

 

BFS는 큐 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다

① 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

② 큐에서 노드를 꺼낸 뒤에 해당 노드이 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.

③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

▒ BFS.py ▒

from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[v] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
               if not visited[i]:
                queue.append(i)
                visited[i] = True
 
    # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
    graph = [
            [],
            [2,3,8],
            [1,7],
            [1,4,5],
            [3,5],
            [3,4],
            [7],
            [2,6,8],
            [1,7]
            
    ]
 
    # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
    visited = [False] * 9
 
    # 정의된 DFS 함수 호출
    dfs(graph, 1, visited)

import java.util.*;
 
public class Main {
 
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
 
    // BFS 함수 정의
    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;
                }
            }
        }
    }
 
    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }
 
        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);
 
        bfs(1);
    }
 
}

---

---