BFS (Breath First Search) 너비우선탐색 Python 인접리스트 활용

너비우선탐색 BFS (Breadth First Search) 큐를 이용하여 그래프를 순회하는 방법

 

1. 1번부터 접근을 시작한다 가정했을 때 1번의 인접리스트를 큐에 저장 (모든 노드가 자신의 인접리스트를 큐에 저장 단, 이전에 방문한적이 없으며, Queue에 저장이 안되어 있는 경우 Queue에 저장함)

 

2. 자신의 모든 노드에 대해 Queue 저장 작업이 완료되면 할 일을 다했다. 이제 Queue의 pop연산을 수행하고 pop한 노드 및 정점의 인접리스트에 대해 1번의 과정을 수행한다.

 

3. 큐가 비어있지 않는 한 위 과정을 반복적으로 수행

 

1번부터 BFS시 수행되는 순서는 다음과 같다.

1 2 4 3 11 9 5 6 8 7 10 

 

아래의 소스코드를 통해 각 정점 및 노드별 큐의 상태를 확인할 수 있다.

 

 

# m = 11, e = 13
'''
11 13
1 2
1 4
2 3
2 4
2 11
3 5
3 6
4 9
5 6
6 7
7 8
8 9
8 10
'''
 
m,e = map(int, input().strip().split())
lists = []
queue = []
visited = []
result = []
 
def bfs(n):
    visited.append(n)
    queue.append(n)
    while len(queue) != 0:
        n = queue.pop(0)
        result.append(n)
        visited.append(n)
        print(n, end=" ")
        for i in lists[n]:
            if i not in visited and i not in queue:
                queue.append(i)
        print(queue)
 
 
#### [[],[],[],[],[]] ....
for i in range(m+1):
    for j in range(m):
        lists.append([])
 
# 서로 간선을 관계를 지어줌
for i in range(e):
    a, b = map(int, input().strip().split())
    lists[a].append(b)
    lists[b].append(a)
 
bfs(1)
print("")
for i in result:
    print(i, end=" ")