[graph] BFS 기본 구현

문제



접근

import sys
sys.stdin = open('input.txt')

from collections import deque

V, E = map(int, input().split()) # 7, 8
edge = list(map(int, input().split())) # [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]


# 인접 행렬을 만든다.
graph = [[0]*(V+1) for _ in range(V+1)] # (V+1 * V+1) 행렬
for i in range(E):
    ni, nj = edge[2*i], edge[2*i+1]
    graph[ni][nj] = 1
    graph[nj][ni] = 1  # 무방향 그래프


# 큐와 visited 설정한다.
deque_que = deque()
visited = [False] * (V+1)


def BFS(graph, start_node):
    # 시작 노드를 큐에 넣고 방문처리한다.
    deque_que.append(start_node)
    visited[start_node] = True

    # 큐가 빌 때까지
    while deque_que:
        # 1. 큐의 첫번째 원소를 반환한다.
        node = deque_que.popleft()
        # 출력
        print(node)
        # 2. node와 연결된 모든 선을 돌면서
        for w in range(1, V+1):
            # 아직 방문하지 않은 곳이면
            if graph[node][w] == 1 and not visited[w]:
                # 방문표시하고 큐에 넣는다.
                visited[w] = True
                deque_que.append(w)

BFS(graph, 1)