BFS 설명 및 구현 with 파이썬

※ BFS란?

 

BFS.

 

Breadth First Search

 

말그대로 너비 우선 탐색

 

그래프에서 가장 가까운 노드부터 먼저 탐색한다

 

 

※ BFS구현?

- BFS는 큐를 통해서 구현한다

 

 

※ BFS 과정은?

 

1. 탐색을 시작할 노드를 큐에 삽입하고 방문 처리한다

2. 큐에서 노드를 꺼낸다. 인접한 노드 중에 방문하지 않은 노드가 있으면 모두 큐에 넣고 방문 처리한다

3. 더이상 2번을 수행할 수 없을 때까지 반복한다.

 

※ BFS 구현

def bfs(graph, v, visited):
    queue = deque()

    visited[v] = True
    print(v,"방문했음")
    queue.append(v)

    while len(queue) != 0:
        for i in graph[queue.popleft()]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                print(i,"방문했음")



graph = [
    [],
    [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)