[개념/파이썬/알고리즘] BFS(Breadth First Search)

BFS

• 한 경우에 대한, 모든 가능한 경우의 수를 탐색한다.
• Queue를 이용한다.
• 최단거리(최단경로)를 탐색하는 대표적인 알고리즘 중 하나이다.
• 완전탐색 알고리즘 중 , 하나이다.
• 방문했던 Node는 방문하지 않는다.
• Web crawling,SNS,Network broadcasting,grabage collection 등에 이용된다고 합니다.

매 단계에서 가능한 모든 경우의 수를 확인한다.(BFS)

순서: A->B->C ->D ->E->F ->G ->H ->J -> J -> K

 

BFS는 큐를 사용합니다! Queue를 이용해서, 어떻게 탐색하는지 봅시다.

큐에서도 2가지 동작이 있습니다.

• popleft: 큐의 왼쪽에서 노드를 꺼냅니다.
• appendleft:큐의 왼쪽에 노드를 추가합니다.

popleft 하면서, 자식 노드들을 추가하면서, 하나하나씩 출력합니다!

 

코드로 구현하면?

from collections import deque
 v,e = map(int,input().split())
 adj=[[] for _ in range(v)]
 v_check = [False for _ in range(v)] 
 
 for i in range(e):
 	start,end=map(int,input().split())
    adj[start].append(end)
    adj[end].append(start)
 
def bfs():
    queue = deque([0]) 
    # 첫번째 원소 넣어주고, 바로 START!
    #인접리스트로 만들었기 때문에, check도 , 1차원배열 느낌으로 만들어줘야함.
    b_check[start] = True
    while queue:
        v = queue.popleft()
        #print(v, end = ' ')
        for i in edge[v]:
            if not b_check[i]:
                v_check[i] = True
                queue.append(i)