DFS/BFS 실제

1) DFS 그래프 탐색 python 코드 구현

def dfs(graph, vertex, visited):
    # 재귀적으로 처리하는 DFS
    visited[vertex] = 1
    print('{0} '.format(vertex))

    # 연결된 다른 노드 방문
    for n in graph[vertex]:
        if visited[n] == 0:
            dfs(graph, n, visited)


if __name__ == '__main__':
    graph = [
        [],
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]
    ]
    visited = [0] * 9

    dfs(graph, 1, visited)

스택이 아닌 재귀호출을 이용한 DFS 구현

2) BFS 그래프 탐색 python 코드 구현

from collections import deque

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

    while queue:
        visit = queue.popleft()
        print('{0} '.format(visit))
        for n in graph[visit]:
            if visited[n] == 0:
                queue.append(n)
                visited[n] = 1

if __name__ == '__main__':
    graph = [
        [],
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1, 7]
    ]

    visited = [0] * 9

    bfs(graph, 1, visited)

데크를 이용한 BFS 구현