[Algorithm] DFS/BFS - 2

BFS(BBreadth First Search - 너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘

큐 자료 구조 사용

 

위의 예시로 사용 될 경우, 

결과 예시는 1,2,3,8,7,4,5,6이 됨

 

[코드 예시]

from collections import deque

def bfs(graph, v, visited):

    q = deque([v])
    
    visited[v] = True # 현재 노드 방문 처리
    
    while q: ## queue가 빌 떄 까지 반복
        p = q.popleft() ## 하나 먼저 뽑고
        
        for i in graph[p]:
            if not visited[i]: ## 방문하지 않았다면 
                q.append(i) # 큐에 삽입하고
                visited[i] = True # 방문 처리
                



graph = [
    [],
    [2,3,8], # 1의 노드에는 2,3,8이 달려있다는 뜻
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9 ## 방문 여부 리스트

bfs(graph,1, visited)

REF : 나동빈, 이것이 코딩테스트다