[Algorithm] 너비 우선 탐색 (BFS, Breadth-first Search)

그래프 (Grpah)

함수 그래프 != 그래프 이론의 그래프

• 함수 그래프 : x(정의역), y(치역)에 해당하는 값을 좌표 상에 표시하는것
• 그래프 이론의 그래프 : *꼭짓점(Vertex)과 간선(Edge)으로 구성, G = (V, E)

*꼭짓점(Vertex) == 노드(Node)

 

+추가

- 그래프에는 간선이 화살표 => 단방향, 실선인 경우 => 양방향 그래프

- 간선에 가중치를 주는 경우도 있음, 아무것도 쓰여있지 않으면 모두 1이거나 같은 가중치

---

너비 우선 탐색 (BFS, Breadth-forst Search)

: 연결되어있는(인접한) 노드를 우선적으로 탐색하는 것이다. 자료구조 *큐(queue) 를 사용하여 구현할 수 있으며 과정은 현재 노드와 연결된 노드를 큐에 append 후 큐의 가장 처음 노드부터 인접 노드 검색, 방문하지 않은 인접 노드가 있으면 큐에 추가하고 이 과정을 큐가 빌때까지 수행한다. 

 

* 큐(Queue)

• 선입선출 (FIFO, First In First Out)
• 라이브러리 : from collections import deque
• append(), popleft()

• 인접행렬 or 인접리스트 -> 노드, 엣지의 정보가 들어있음
• 방문 확인 리스트 -> 노드를 방문 했다면 해당 노드를 방문 확인 리스트에 추가
• 큐 -> 가장 처음 노드를 popleft하고 현재 노드와 연결되어있고 방문하지 않은 노드를 큐에 append
  => queue가 빌때까지

**항상 같은 결과를 내기 위해서 여기에서는 노드를 오름차순으로 방문하였음**

 

수행단계

노드, 간선정보 저장 (grqph)

방문리스트, 큐 정의 (visited, queue)

 

시작노드(s_node)를 방문처리 & 큐에 append

while 큐가 차있음

   큐의 가장 앞선 노드 (node)를 꺼낸다

    for 가장 앞선 노드에 연결된 노드 탐색 

        if 방문하지 않은 노드가 있다면 

            큐에 append, 방문처리

from collections import deque

def bfs(graph, s_node, visited, queue):
    queue.append(s_node) 
    visited[s_node] = True
   
    while queue:
        node = queue.popleft()
        print(node)    
        for i in sorted(graph[node]):
            if not visited[i]: 
                queue.append(i)
                visited[i] = True
    
graph = [[],[2,3],[1],[1,4,5],[3,5],[4,3]]
visited = [False]*len(graph)
queue = deque()
    
bfs(graph, 1, visited, queue)