BFS

1. deque 라이브러리

from collections import deque

큐를 만들기 위해 덱 라이브러리를 사용한다

 

2. bfs 함수

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start]=True
    while queue:
        v=queue.popleft()
        print(v, end='')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

시작 노드의 visited를 True로 해준다

큐가 빌 때까지 아래 과정을 반복한다

큐 맨 아래 원소를 출력하고,

출력한 노드의 연결 노드들 중 방문하지 않은 노드를 큐에 삽입하고 visited를 True로 해준다

 

start=1일 경우,

visited[1] = True

 

graph=[
    [], #
    [2, 3, 8], # 1 node와 연결된 노드들 # v=1이고 2,3,8 노드를 방문하지 않았으므로 queue에 2,3,8 삽입하고 visited를 True로 한다 # 2가 가장 왼쪽에 있으므로 다음 v=2이다
    [1, 7], # 2 node와 연결된 노드들
    [1, 4, 5], # 3 node
    [3, 5], # 4 node
    [3, 4], # 5 node
    [7], # 6 node
    [2, 6, 8], #7 node
    [1, 7] # 8 node
]

 

3. graph 리스트 만들기

graph=[
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

노드의 편의성을 위해 첫번째는 [ ]로 해준다

1번노드 [2,3,8] 연결, 2번 노드 [1,7] 연결 ...

그림으로 나타낸 graph 모습

bfs 탐색을 하면 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

 

4. visited

visited=[False] * 9

노드 개수 만큼 visited 리스트를 만들어준다

 

5. bfs 탐색

bfs(graph,1,visited) #12387456

1. bfs(graph, 1, visited)

def bfs(graph, start, visited):
    queue = deque([start]) # start = 1
    visited[start]=True # visited = [0,1,0,0,0,0,0,0,0]

 

queue 모습

 

2. v=1

 while queue: # queue가 존재할 때까지
        v=queue.popleft() # v = 1 
        print(v, end='') # 1 출력

        for i in graph[v]: # graph[1]인 [2,3,8]에서
            if not visited[i]: #2,3,8 -> false
                queue.append(i) # 2,3,8 삽입
                visited[i]=True # visited = [0,1,1,1,0,0,0,0,1]

 

v=1에서 queue 모습

 

3. v=2

 while queue: # queue가 존재할 때까지
        v=queue.popleft() # v = 2
        print(v, end='') # 2 출력

        for i in graph[v]: # graph[2]인 [1,7]에서
            if not visited[i]: #7 -> false
                queue.append(i) # 7 삽입
                visited[i]=True # visited = [0,1,1,1,0,0,0,1,1]

 

v=2에서 queue 모습

 

4. v=3

 while queue: # queue가 존재할 때까지
        v=queue.popleft() # v = 3
        print(v, end='') # 3 출력

        for i in graph[v]: # graph[3]인 [1,4,5]에서
            if not visited[i]: # 4,5 -> false
                queue.append(i) # 4,5 삽입
                visited[i]=True # visited = [0,1,1,1,1,1,0,1,1]

 

v=3에서 queue 모습

 

4. v=8

 while queue: # queue가 존재할 때까지
        v=queue.popleft() # v = 8
        print(v, end='') # 8 출력

        for i in graph[v]: # graph[3]인 [1,7]에서
            if not visited[i]: # x -> false
                queue.append(i)
                visited[i]=True

 

v=8에서 queue 모습

 

5. v=7

위의 과정 반복

 

 

 

 

 

<전체코드>

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start]=True
    while queue:
        v=queue.popleft()
        print(v, end='')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

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)