알고리즘 BFS(너비우선탐색)

 

 

 

# BFS
- 너비 우선 탐색(Breadth-First Search, BFS)은 그래프를 탐색하기 위한 대표적인 알고리즘 중 하나로, 시작 노드로부터 가까운 노드부터 차례대로 탐색하는 방식(자기 자식을 우선 탐색)
- Graph:Vertex(어떤것)+Edge(이어지는것)
- 해당 알고리즘은 그래프 탐색, 최단 경로 찾기, 네트워크 트래픽 경로 계산 등에 활용
- 주로 Queue 자료구조를 활용하여 구현
- Queue는 리스트의 한쪽 끝에는 삽입 작업이 이루어지고 한쪽 끝에는 삭제 작업이 이루어지는 선입선출FIFO 구조로 운영되는 유한 순서 리스트

## 시간복잡도
- BFS: o(v+e)
- vertex 계산 + edge 갯수

출처: C로 배우는 쉬운 자료구조

 

BFS의 순회경로는 다음과 같다.

1. A를 방문

2. A 인접 정점 B,C 방문

3.B에서 인접 정점 D,E 방문

4. G 방문

5. F 방문

 

.. 이라는데 작년에 수업을 들었는데도 사실 잘 모르겠다.. 에휴 

 

 

#gpt 활용
from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 저장하기 위한 집합
    queue = deque([start])  # 큐에 시작 노드를 넣고 시작

    while queue:
        current_node = queue.popleft()  # 큐에서 노드를 하나 꺼내옴

        if current_node not in visited:
            print(current_node, end=' ')  # 노드를 방문하면 출력
            visited.add(current_node)  # 방문한 노드를 집합에 추가

            # 현재 노드의 인접한 노드들을 큐에 추가
            queue.extend(neighbor for neighbor in graph[current_node] if neighbor not in visited)

# 간단한 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}

start_node = 'A'
print("BFS 결과:")
bfs(graph, start_node)

 

popleft가 뭔가 해서 찾아봤더니 

popleft 함수는 collections 모듈의 deque 클래스에서 제공되는 메서드 중 하나입니다.
popleft는 덱(Deque)의 왼쪽에서 요소를 제거하고 반환하는 함수입니다.

재방문 방지를 위해 사용되는 함수같음.. 

 

알고리즘 공부는 계속 해봐야겠다.