[Algo] BFS 기초 예제와 코드 구현 (python)

관련 백준 문제

(1260번) DFS와 BFS

Python으로 BFS구현

인접 리스트 생성

입력 받으면서 그래프의 정점간의 관계를 나타내는 인접 리스트까지 생성해주기

from collection import deque # deque를 활용하여 queue 구현

n, m , v = map(int, input().split()) # n : 노드(정점), m(간선), v(시작점)

graph = [[] for _ in range(n + 1)] # 0번 노드는 사용하지 않으니 1~n번 노드까지 할당
for i in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for i in range(1, n + 1):
    graph[i].sort() # 순서 보정을 위해 오름차순 정렬 필요

BFS 함수 작성

queue를 사용하여 bfs를 구현한다

def bfs(start):
    queue = deque()
    visited = [0 for _ in range(n + 1)]
    queue.append(start)
    visited[start] = 1
    while len(queue) > 0:
        curr = queue[0]
        print(curr, end=' ')
        for nxt in graph[curr]:
            if visited[nxt] == 0:
                visited[nxt] = 1
                queue.append(nxt)
        queue.popleft()

전체 코드

from collections import deque

n, m, v = map(int, input().split())

# 인접 리스트
graph = [[] for _ in range(n+1)] # 1번부터 n번까지 정점 사용

# 간선 처리
for i in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1) # 단방향이면 이거 주석처리 하면 됨

for i in range(1, n+1):
    graph[i].sort() # 순서 보정을 위해 오름차순 정렬 필요

def bfs(start):
    queue = deque()
    visited = [0 for _ in range(n + 1)]
    queue.append(start)
    visited[start] = 1
    while len(queue) > 0:
        curr = queue[0]
        print(curr, end=' ')
        for nxt in graph[curr]:
            if visited[nxt] == 0:
                visited[nxt] = 1
                queue.append(nxt)
        queue.popleft()

bfs(v)