[python] DFS(깊이우선탐색) / BFS(너비우선탐색)

1️⃣ DFS

DFS는 Depth-First Search 깊이우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

• DFS 동작과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
• 인접행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  • 예제

  # 인접행렬 방식 예제
  INF = 99999999
  
  graph=[
      [0,7,5],
      [7,0,INF],
      [5,INF,0]
  ]
  
  print(graph)
  

• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식👉 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할때에도 단순히 2차원 리스트를 이용하면 된다는 점을 기억하자.
  • 예제

  graph=[[] for _ in range(3)]
  
  # 노드 0에 연결된 노드 정보 저장(노드, 거리)
  graph[0].append((1,7))
  graph[0].append((2,5))
  
  # 노드 1에 연결된 노드 정보 저장(노드, 거리)
  graph[1].append((0,7))
  
  # 노드 2에 연결된 노드 정보 저장(노드, 거리)
  graph[2].append((0,5))
  
  print(graph)
  

• 인접 리스트는 ‘연결리스트’라는 자료구조를 이용해 구현하는데 C++, JAVA와 같은 프로그래밍 언어에서는 별도로 연결 리스트 기능을 위한 표준 라이브러리를 제공한다. 반면에 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공한다.
• DFS 예제

def dfs(graph,v,visited):
    # 현재 노드를 방문 처리
    visited[v]=True
    print(v,end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)
            
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False]*9

dfs(graph,1,visited)

 

 

2️⃣ BFS

BFS (Breadth First Search) 알고리즘은 ‘너비 우선 탐색’이라는 의미를 가진다. 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다, BFS는 그 반대이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하며 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

• BFS 동작 방식
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
• BFS 예제

from collections import deque

# BFS 메서드 정의 
def bfs(graph,start,visited):
    # 큐(queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start]=True
    
    #큐가 빌 때까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v,end='  ')
        # 해당 원소와 연결된 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
                
                
graph =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False]*9

bfs(graph,1,visited)