DFS, BFS with python

Depth Frist Search(DFS)와 Breadth First Search(BFS)는 그래프 탐색 알고리즘이다.

각각 특정 순서에 따라 그래프의 노드를 탐색하게 된다.

DFS는 stack 또는 재귀호출을 이용하여 구현하고 BFS는 queue를 이용하여 구현한다.

 

1. DFS 구현방법

1. stack에 시작 노드를 넣고 해당 노드를 방문했음을 기록한다. 
2. stack의 최상단 노드와 인접한 노드 중 아직 방문하지 않은 노드의 존재 여부에 따라
   • 인접한 노드 A가 있으면 stack에 넣고 노드 A를 방문했음을 기록한다.
   • 인접한 노드가 없으면 stack에 대해 pop연산을 진행한다.
3. stack이 empty 상태가 되면 알고리즘을 종료한다.

★ 노드가 stack에 push될 때마다 push되는 노드를 순서대로 리스트에 저장하면 방문 순서를 확인할 수 있다.

 

2. BFS 구현방법

1. queue에 시작 노드를 넣고 해당 노드를 방문했음을 기록한다.
2. queue 첫번째 노드와 인접한 노드 중 아직 방문하지 않은 노드의 존재 여부에 따라
   • 인접한 노드 A가 있으면 queue에 넣고 노드 A를 방문했음을 기록한다.
   • 인접한 노드가 없으면 queue에 대해 popleft한다. 
3. queue가 empty 상태가 되면 알고리즘을 종료한다.

노드가 queue에 insert 될 때마다 insert되는 노드를 리스트에에 저장하면 방문 순서를 확인해볼 수 있다.

 

 

★ 통상적으로 동일한 레벨에 방문하지 않은 노드가 여러개 있는 경우 가장 낮은 번호의 노드부터 방문하도록 하는 것이 관례라고 하니 여기서도 동일하게 구현하도록 한다.

 

 

 

재귀 호출을 사용한 DFS 구현

# define DFS method
def dfs(graph, v, visited):
  # make current node status to visited
  visited[v] = True
  print(v, end = ' ')
  # recursively visit adjacency nodes of curret node.
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

# adjacency list of graph
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# a list that save visited status
visited = [False] * 9

# call DFS method
dfs(graph, 1, visited)

 

 

반복문을 사용한 DFS 구현

# adjacency list of graph
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# a list that save visited status
visited = [False] * 9


def dfs_first(start_node):
    stack = list()
    stack.append(start_node)
    global graph, visited
    dfs(stack, graph, visited)


def dfs(stack, g, v):
    while len(stack) > 0:
        current_node = stack.pop()
        v[current_node] = True
        print(current_node, end=' ')
        for i in reversed(g[current_node]): # because it is necessary for pop more little value first, reverse the list.
            if not v[i] and i not in stack:
                stack.append(i)


dfs_first(1)

 

 

BFS 구현

from collections import deque

# adjacency list of graph
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# a list that save visited status
visited = [False] * 9


# define bfs method
def bfs(graph, start, visited):
    # use deque library to implement queue
    queue = deque([start])
    # make visited node for current node
    visited[start] = True
    # util queue is empty
    while queue:
        # remove first one of queue elements
        v = queue.popleft()
        print(v, end=' ')
        # insert the element that is not visited to queue
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


bfs(graph, 1, visited)

 

 

백준에서 제공하는 DFS, BFS 문제와 풀이.

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

from sys import stdin
# N: Node의 개수 (1 <= N <= 1,000)
# M: Edge의 개수 (1 <= M <= 10,000)
# V: 시작 Node 번호
N, M, V = map(int, stdin.readline().strip().split())    # stdin library를 사용하여 빠르게 입력받습니다.
edge = [[] for _ in range(N+1)]   # 각 node별로 인접한 node의 연결 정보를 나열한 adjacency list를 초기화합니다.

for _ in range(M):  # 사용자의 입력 정보대로 adjacency list를 만듭니다.
    n1, n2 = map(int, stdin.readline().strip().split())   # 인접 리스트를 작성할 때는 양방향 연결임에 주의해야합니다.
    # 즉, node1과 node2가 인접해있는 경우 node1에서 바라볼 때와 node2에서 바라볼 때 모두를 고려하여 인접 리스트를 작성합니다.
    edge[n1].append(n2)   # n1 -> n2
    edge[n2].append(n1)   # n2 -> n1

for e in edge:
    e.sort(reverse=True)    # 오름차순으로 node를 방문하기 위해 인접 리스트를 사전에 내림차순으로 정렬해 둡니다.


def dfs():
    d_visit = []    # 각 node의 방문순서를 고려한 출력을 위해 방문 순서를 기록해둘 리스트를 선언합니다. 
    stack = [V]     # dfs를 위한 stack으로 리스트를 사용합니다.
    d_check = [0 for _ in range(N+1)]   # node 방문 이력을 기록하기 위한 리스트를 선언하고 모두 0으로 초기화 합니다.
    while stack:    # stack이 비어있지 않는 동안 이하의 로직을 실행합니다.
        v1 = stack.pop()        # 1. stack에서 node를 pop합니다.
        if not d_check[v1]:     # 2. pop한 node가 방문한 node가 아닌 경우  
            d_check[v1] = 1     # 3. 해당 node를 방문처리 하고
            d_visit.append(v1)  # 4. 출력용 리스트에 node를 추가합니다.
            stack += edge[v1]   # 5. 기존 stack에 pop한 node의 인접 node들을 push합니다.
    return d_visit  # 방문순서 출력용 리스트를 반환합니다.


def bfs():
    b_visit = []
    queue = [V]     # bfs를 위한 queue로 리스트를 사용합니다.
    b_check = [0 for _ in range(N+1)]
    b_check[V] = 1  # 시작 node를 방문처리 합니다.
    while queue:    # queue가 비어있지 않은동안 이하의 로직을 실행합니다.
        v2 = queue.pop()    # 1. 리스트에서 node를 pop합니다.
        b_visit.append(v2)  # 2. pop한 node를 출력용 리스트에 넣어줍니다.
        for i in reversed(edge[v2]):    # 3. 방문한 node와 인접한 node들을 오름차순으로 순회하며 이하의 로직을 실행합니다.
            if not b_check[i]:  # 3-1. 인접 node가 아직 방문 이력이 없는 경우
                b_check[i] = 1  # 3-2. 방문 처리를 진행하고
                queue = [i] + queue     # 3-3. 리스트에서 데이터가 나가는 방향은 queue와 반대이므로 queue 리스트 선단에 방문 node를 붙여줍니다.
    return b_visit


print(' '.join(map(str, dfs())))
print(' '.join(map(str, bfs())))