[Data Structure / Algorithms] BFS(Breadth-First Search)

전성훈·2023년 11월 13일

Algorithms swift

Data Structure-Algorithm

목록 보기

26/35

주제: 너비 우선 탐색(BFS: Breadth-First Search)

BFS란?

BFS 알고리즘은 '너비 우선 탐색'이라는 의미를 가집니다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘입니다.
BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석입니다.
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 됩니다.

추가 세부사항

레벨별 탐색

BFS는 시작 정점에서 가장 가까운 정점부터 차례대로 모든 정점을 방문합니다. 이 과정에서 각 정점은 "Level"이라고 하는 개념으로 분류할 수 있으며, 이는 시작 정점으로부터의 거리에 해당합니다.
경로 탐색

BFS는 최단 경로를 찾는 데 자주 사용됩니다. 예를 들어, 미로 찾기, 최단 경로 문제 등에서 활용됩니다. BFS를 사용하면 시작 정점으로부터 각 정점까지의 최단 경로를 찾을 수 있습니다.
사이클 탐지

BFS는 그래프 내의 사이클을 탐지하는 데에도 사용될 수 있습니다. 그래프 탐색 중에 이미 방문한 정점을 다시 방문하게 되면 사이클이 존재한다고 볼 수 있습니다.
레벨별 탐색 응용

BFS는 레벨별 탐색 특성을 이용하여 여러 응용 프로그램에서 사용됩니다. 예를 들어, 소셜 네트워크에서 사용자 간의 연결 단계를 찾는 데 사용될 수 있습니다.

동작 방식

탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다.
2번 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

활용

최소 스패닝 트리 생성
두 정점 사이의 가능한 경로 찾기
두 정점 사이의 최단 경로 찾기 등

성능

BFS를 사용하여 그래프를 탐색할 때 각 장점은 한 번씩 큐에 저장된다는 것입니다. 이 과정은 O(V)(정점)의 시간 복잡도를 가집니다. 이 동안에는 모든 엣지를 방문합니다.
모든 엣지를 방문하는데 걸리는 시간은 O(E)(간선)입니다.
결국, BFS의 시간복잡도는 O(V + E)입니다.
BFS의 공간 복잡도는 주로 큐에 저장되는 정점의 수에 따라 달라집니다. 최악의 경우, 모든 정점이 큐에 저장될 수 있으므로 O(V) 입니다.
BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하며, 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편입니다.
BFS는 무방향 그래프와 방향 그래프 모두에 적용될 수 있습니다. 무방향 그래프에서는 각 간선이 양방향으로 고려되며, 방향 그래프에서는 각 간선의 방향을 고려하여 탐색합니다.

구현

Graphs와 연동

struct QueueStack<T> {
    var leftStack: [T] = []
    var rightStack: [T] = []
    
    public init() { }
    
    public var isEmpty:Bool {
        leftStack.isEmpty && rightStack.isEmpty
    }
    
    public var peek: T? {
        !leftStack.isEmpty ? leftStack.last : rightStack.first
    }
    
    public mutating func enqueue(_ element: T) {
        rightStack.append(element)
    }
    
    public mutating func dequeue() -> T? {
        if leftStack.isEmpty {
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        return leftStack.popLast()
    }
}
extension Graph where Element: Hashable { 
	func breadthFirstSearch(from source: Vertex<Element>) -> [Vertex<Element>] { 
		var queue = QueueStack<Vertex<Element>>()
		var enqueued: Set<Vertex<Element>> = []
		var visited: [Vertex<Element>] = []
		
		queue.enqueue(source)
		enqueued.insert(source)
		
		while let vertex = queue.dequeue() { 
			visited.append(vertex)
			let neighborEdges = edges(from: vertex)
			neighborEdges.forEach { edge in 
				if !enqueued.contains(edge.destination) { 
					queue.enqueue(edge.destination)
					enqueue.insert(edge.destination)
				}
			}
		}
		return visited 
	}
}

큐는 방문할 다음 인접 정점을 확인합니다.
enqueued는 큐에 이미 들어간 정점을 기억하며, 같은 정점이 두 번 큐에 들어가지 않도록 합니다. 여기서는 lookup이 O(1)로 빠른 Set 타입을 활용 합니다.
visited는 정점 탐색 순서를 저장하는 배열입니다.

set을 사용하는 이유

중복 방지
- BFS에서는 같은 정점을 두 번 이상 탐색하지 않도록 해야 합니다. Set을 사용하면 이미 큐에 추가된 정점을 효율적으로 관리하고 중복을 방지할 수 있습니다.
효율적인 검색
- Set의 검색 시간 복잡도는 O(1) 입니다. 따라서 큐에 정점을 추가하기 전에 해당 정점이 이미 추가되었는지 빠르게 확인할 수 있습니다.
알고리즘 성능 향상
- Set을 사용하면 전체적인 BFS 알고리즘의 효율성이 향상됩니다. 특히 정점의 수가 많은 그래프에서 성능 차이가 두드러집니다.

Set를 사용하지 않고 visited만 활용하기

 func noSetBFS(from source: Vertex<Element>) -> [Vertex<Element>] {
        var queue = QueueStack<Vertex<Element>>()
        var visited: [Vertex<Element>] = []
        
        queue.enqueue(source)
        visited.append(source)
        
        while let vertex = queue.dequeue() {
            
            let neighborEdges = edges(from: vertex)
            
            neighborEdges.forEach { edge in
                if !visited.contains(edge.destination) {
                    queue.enqueue(edge.destination)
                    visited.append(edge.destination)
                }
            }
        }
        
        return visited
    }
    
print(graph2.breadthFirstSearch(from: tokyo2))
print(graph2.noSetBFS(from: tokyo2))

[1: Tokyo, 3: Detroit, 5: Washington DC, 6: Austin Texas, 7: Seattle, 4: San Francisco]
[1: Tokyo, 3: Detroit, 5: Washington DC, 6: Austin Texas, 7: Seattle, 4: San Francisco]

위 두 코드에 차이점은 set 집합으로 선언한 enqueued와 배열 집합으로 선언한 visited 간 containes의 시간 복잡도입니다.

Int형 2차원 리스트에서 BFS 활용하기

Set을 활용한 BFS

let testGraph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

var visited: [Int] = []

func bfs(_ graph: [[Int]], _ start: Int) {
    var queue = QueueStack<Int>()
    var enqueued: Set<Int> = []
    
    queue.enqueue(start)
    enqueued.insert(start)
    
    while let value = queue.dequeue() {
        visited.append(value)

        for i in graph[value] {
            if !enqueued.contains(i) {
                queue.enqueue(i)
                enqueued.insert(i)
            }
        }
    }
}

bfs(testGraph, 1)

[1, 2, 3, 8, 7, 4, 5, 6]

print(visited)

Set을 사용하지 않고 visited 배열만을 활용한 bfs


let testGraph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

var visited = [Bool](repeating: false, count: testGraph.count)

func bfs(_ graph: [[Int]], _ start: Int) {
    var queue = QueueStack<Int>()
    
    queue.enqueue(start)
    visited[start] = true
    
    while let value = queue.dequeue() {
        print(value, terminator: " ")
        for i in graph[value] {
            if !visited[i] {
                queue.enqueue(i)
                visited[i] = true
            }
        }
    }
}


bfs(testGraph, 1)

[1, 2, 3, 8, 7, 4, 5, 6]