그래프 BFS, DFS 알고리즘 (with Python3)

그래프 탐색 알고리즘에는 대표적으로 BFS 와 DFS 가 있다.

 

본 글에서는 아래 그래프를 가지고, BFS 와 DFS 의 탐색 알고리즘을 살펴본다.

그래프

 

1. BFS

너비 우선 탐색을 BFS라 부르고, Breadth Frist Search 의 약자이다.

해당 노드와 같은 레벨(Level)의 노드를 먼저 탐색을 하기 때문에 붙여진 이름이다.

 

위 그래프를 예로 탐색 순서를 나열하면, 아래와 같은 순서로 탐색을 하게된다.

• A - B - C - D - E - F - G - H - I - J - K - L - M

1.1. 코드

아래 코드는 unittest 기반으로 작성했다. 알고리즘은 bfs() 메소드를 참고한다.

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import unittest


def bfs(graph, start):
    """너비 우선 탐색 알고리즘"""
    queue = [start]  # 초기값은 시작 노드
    visit = list()  # 방문했던 노드는 다시 재방문 하지 않기 위해 저장

    while queue:
        node = queue.pop(0)  # 큐에서 노드를 꺼내온다.

        if node not in visit:  # 방문하지 않은 노드인 경우, 방문한다.
            visit.append(node)  # 방문 리스트에 추가한다.

            # 큐에 인접한 노드들을 추가한다.
            queue.extend(graph[node])
            # .extend()는 아래 코드와 동일하다
            # for new_node in graph[node]:
            #     queue.append(new_node)

    return visit

# ...

class Exam15(unittest.TestCase):

    @classmethod
    def setUp(cls):
        cls.graph = {
            "A": ["B"],
            "B": ["A", "C", "D"],
            "C": ["B", "E", "F"],
            "D": ["B", "G", "H"],
            "E": ["C"],
            "F": ["C", "I"],
            "G": ["D"],
            "H": ["D", "J", "K"],
            "I": ["F", "L"],
            "J": ["H", "M"],
            "K": ["H"],
            "L": ["I"],
            "M": ["J"],
        }

    def test_bfs(self):
        self.assertEqual(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"], bfs(self.graph, "A"))

# ...


if __name__ == "__main__":
    unittest.main()

 

BFS 응용하기 2020/04/01 - [Algorithm] - 탐색 알고리즘 BFS 응용하기 (친밀도 구하기)

2. DFS

깊이 우선 탐색을 DFS 라 부르고, Depth First Search 의 약자이다.

BFS 와 반대로 해당 노드의 자식 노드를 먼저 탐색하는 차이점이 있다.

 

위 그래프를 예로 탐색 순서를 나열하면, 아래와 같은 순서로 탐색을 하게된다.

• A - B - C - E - F - I - L - D - G - H - J - M - K

2.1. 코드

아래 코드는 unittest 기반으로 작성했다. 알고리즘은 dfs() 메소드를 참고한다.

      

      

      

    
    

      <python />
    
# -*- coding: utf-8 -*-

import unittest

# ...

def dfs(graph, start):
    """깊이 우선 탐색 알고리즘"""
    stack = [start]
    visit = list()

    while stack:
        node = stack.pop()

        if node not in visit:
            visit.append(node)

            # 아래와 같이 해도 DFS 이지만, 오른쪽에서 왼쪽으로 탐색을 해서 결과값이 다르게 나온다.
            # stack.extend(graph[node])  # ["A", "B", "D", "H", "K", "J", "M", "G", "C", "F", "I", "L", "E"]

            # 왼쪽에서 오른쪽 탐색을 위해, reversed()를 이용해 연순으로 바꿔준다.
            stack.extend(reversed(graph[node]))

    return visit


class Exam15(unittest.TestCase):

    @classmethod
    def setUp(cls):
        cls.graph = {
            "A": ["B"],
            "B": ["A", "C", "D"],
            "C": ["B", "E", "F"],
            "D": ["B", "G", "H"],
            "E": ["C"],
            "F": ["C", "I"],
            "G": ["D"],
            "H": ["D", "J", "K"],
            "I": ["F", "L"],
            "J": ["H", "M"],
            "K": ["H"],
            "L": ["I"],
            "M": ["J"],
        }

# ...

    def test_dfs(self):
        self.assertEqual(["A", "B", "C", "E", "F", "I", "L", "D", "G", "H", "J", "M", "K"], dfs(self.graph, "A"))


if __name__ == "__main__":
    unittest.main()

 

미로찾기 알고리즘 2020/04/01 - [Algorithm] - 미로 찾기 알고리즘 BFS, DFS (with Python3)