탐색 알고리즘 정리 #1 - BFS(너비 우선 탐색) , DFS(깊이 우선 탐색)

Python 구현 코드

from collections import deque

def DFS(start, stack):
    dfs_visited[start] = True

    for next_node in range(1, N+1):
        if dfs_visited[next_node] == False:
            if adj_list[start][next_node] == 1 or adj_list[next_node][start]==1 :
                stack.append(next_node)
                
                DFS(next_node, stack)
    return stack 

def BFS(start):
    q = deque([start])
    visited = [False]*(N+1)
    visited[start] = True
    
    while q:
        now = q.popleft()
        print(now, end=' ')
        for next_node in range(1,N+1):
            if visited[next_node]==False :
                if adj_list[now][next_node] == 1 or adj_list[next_node][now]==1 :
                    q.append(next_node)
                    visited[next_node] = True
    return

if __name__ == "__main__":
    N, M, start = map(int, input().split())

    adj_list = [[0]*(N+1) for _ in range(N+1)]

    for _ in range(M):
        u,v = map(int, input().split())
        adj_list[u][v] = 1
        adj_list[v][u] = 1

    dfs_visited = [False] * (N+1)

    print(*DFS(start, [start]))
    BFS(start)