BFS, DFS (깊이 우선 탐색, 너비 우선 탐색)

BFS (너비 우선 탐색)

---

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

- 큐를 이용한다.

 

1. 시작 노드를 큐에 넣고 방문처리 한다.

2. 노드를 하나 꺼내고, 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣은 후 방문처리 한다.

3. 더 이상 방문할 점이 없다면 한 층 내려가 인접한 모든 정점들을 방문한다.

 

import java.util.*


val queue: Queue<Int> = LinkedList()
// 이웃 자식을 알아두기 위한 큐
val visited = BooleanArray(100) 
// 정점이 100개라고 가정
val edges = Array(100) { ArrayList<Int>() } 
// 그래프의 인접 리스트

fun bfs(start : Int){
	queue.add(start)
    visited[start] = true
    // 시작 정점 삽입 및 방문 처리
    
    while (queue.isNotEmpty()){
    	val head = queue.poll()
        // 큐의 맨 앞에서 한 개의 정점을 꺼내고 삭제
        for(next in edge[head]){
        // 해당 정점의 간선 진입
        	if(!visited[next]){
            	visited[next] = true
            	queue.add(next)
                // 방문하지 않았다면 꺼내고, 방문 처리
            }	
        }
    }
}

 

관련 알고리즘

- 최소 신장 트리

- 정점 사이 path

- 정점 사이 최단 거리

 

 

 

DFS (깊이 우선 탐색)

---

- 가장 깊은 곳까지 먼저 탐색하는 알고리즘

- 스택 혹은 재귀함수를 이용

- 방문한 노드를 반드시 검사해야 함

 

1. 시작노드를 스택에 삽입 및 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드를 스택에 넣고 방문 처리

3. 더 이상 방문하지 않은 인접노드가 없을 경우 스택에서 최상단 노드 꺼냄

4. 2번의 과정을 더 이상 처리할 수 없으면 종료

 

재귀

val visited = BooleanArray(100) // 정점이 100개라고 가정
val edges = Array(100) { ArrayList<Int>() } // 그래프의 인접 리스트

fun dfs(index: Int) {
    visited[index] = true

    for (next in edges[index]) {
     // 현재 정점과 연결된 모든 정점을 탐색
        if (!visited[next]) {
            dfs(next) 
            // 방문하지 않은 정점에 대해 재귀 호출
        }
    }
}

fun main() {
    // 예시로 간선 추가
    edges[0].add(1)
    edges[0].add(2)
    edges[1].add(3)
    edges[2].add(3)

    dfs(0)
}

 

스택

import java.util.*

val visited = BooleanArray(100) // 정점이 100개라고 가정
val edges = Array(100) { ArrayList<Int>() } // 그래프의 인접 리스트

fun dfsWithStack(start: Int) {
    val stack = Stack<Int>()
    stack.push(start)
    visited[start] = true
    // 시작 정점 넣고 방문처리

    while (stack.isNotEmpty()) {
        val current = stack.pop()
        // 방문 정점을 제거
        for (next in edges[current]) {
        // 현재 정점과 연결된 모든 정점을 탐색
            if (!visited[next]) {
                visited[next] = true
                stack.push(next) 
                // 방문하지 않은 정점은 스택에 추가
            }
        }
    }
}

fun main() {
    // 예시로 간선 추가
    edges[0].add(1)
    edges[0].add(2)
    edges[1].add(3)
    edges[2].add(3)

    dfsWithStack(0)
}

 

 

 

시간 복잡도

---

두 방식 모두 그래프의 모든 간선을 조회하므로,

 

인접 리스트로 표현된 그래프는 O(V+E)

인접 행렬로 표현된 그래프는 O(V^2)

 

간선의 갯수가 노드의 갯수보다 적은 것이 일반적이므로, 인접 리스트 방식이 더 효율적이다.

 

 

 

효율

---

경로의 특징을 저장, 그래프의 규모가 큼 : DFS

최단 거리 : BFS

 

 

출처

https://velog.io/@hyom/DFS-BFS