DFS, BFS Python 구현

2024. 7. 31. 16:17· Algorithm/Graph
목차
  1. 1. DFS 구현
  2. 2. BFS 구현

1. DFS 구현

DFS는 stack으로 구현되며 재귀 함수를 통해 구현할 수 있다.

import sys
input = sys.stdin.readline

def dfs(now, graph, visited):
    visited[now] = True

    print(now, end=' ')
    
    for next in graph[now]:
        if not visited[next]:
            dfs(next, graph, visited)

n, m, start_node = map(int, input().rstrip().split())                                      
graph = [[] for _ in range(n+1)]                       
visited = [False for _ in range(n+1)]

for _ in range(m):                                  
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(n+1):
    graph[i].sort()
    
dfs(start_node, graph, visited)

2. BFS 구현

BFS는 queue를 통해 구현되며 파이썬에서는 deque를 활용한다. 아래와 같이 구현할 수 있다.

import sys
from collections import deque

input = sys.stdin.readline

def bfs(start, graph, visited):
    visited[start] = True

    queue = deque([start])

    while queue:
        now = queue.popleft();
        print(now, end=' ')

        for next in graph[now]:
            if not visited[next]:
                visited[next] = True
                queue.append(next)
    
n, m, start_node = map(int, input().rstrip().split())                                      
graph = [[] for _ in range(n+1)]                       
visited = [False for _ in range(n+1)]

for _ in range(m):                                  
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

bfs(start_node, graph,visited)
저작자표시 (새창열림)

'Algorithm > Graph' 카테고리의 다른 글

[백준] 1987: 알파벳 (python 파이썬)  (0) 2022.11.14
  1. 1. DFS 구현
  2. 2. BFS 구현
'Algorithm/Graph' 카테고리의 다른 글
  • [백준] 1987: 알파벳 (python 파이썬)
코딩마루
코딩마루
코딩마루
Nam's Study Note
코딩마루
전체
오늘
어제
  • 분류 전체보기 (169)
    • BackEnd (88)
      • JSP & Servlet (12)
      • Java (12)
      • JDBC (5)
      • Spring (55)
      • Spring Security (3)
      • AWS (6)
      • Docker (0)
    • FrontEnd (4)
      • HTML (4)
    • Algorithm (23)
      • Brute Force (2)
      • Greedy (2)
      • Graph (2)
      • Dynamic Programming (4)
      • Divide and Conquer (1)
      • Data Structure (11)
    • AI (4)
      • NLP (4)
    • DB (29)
      • Oracle (13)
      • MySQL (15)
    • Data (8)
      • Crawling (8)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
코딩마루
DFS, BFS Python 구현
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.