BFS와 DFS에 대한 설명

• BFS와 DFS는 순회(방문) 하면서 탐색하는 탐색 알고리즘이다
  • 출발지 노드와 그래프/트리 구조에 따라서 탐색하는 순서와 노드가 달라질 수 있음

BFS (Breadth-First-Search) - 너비우선탐색

• 큐의 개념이 적용됨 (FIFO - 선입선출)
  • 큐 - 방문한 노드들을 차례로 저장한 후 꺼낼 수 있음
  • • 딕셔너리, 리스트, 내장함수
• 현재 정점에 연결된 가까운 점들부터 최대한 넓게 탐색
• 장점
  • 노드가 적은 그래프를 순회하거나 최단경로를 탐색할 때 유용
  • 최적해를 찾을 수 있다
• 단점
  • 큐 (Queue) 를 사용하므로 노드가 많아질 때 필요한 메모리 저장공간이 증가함
  • 긴 시간이 걸릴 수 있다
• 노드 S 부터 저장되고 사용
  • 순서 : S->1->2->3->4->5->6->7

• 절차
  • 방문리스트에 시작 노드를 기록
  • 방문하지 않았던 노드는 큐에서 빼면서 방문리스트에 기록
  • 큐에 아무것도 남지 않을 때까지 위의 과정을 반복
  • 모든 노드를 방문처리 할 것
• 활용
  • 길 찾기, 라우팅
  • 웹 크롤러
  • 연결된 구성 요소 찾기

def bfs_queue(start_node, bfs_graph):
    bfslist = [start_node]      # 노드 리스트
    queue = [start_node]      
    
    while queue:                # 큐가 비어 있지 않는지 확인 
        node = queue.pop(0)     # 가장 왼쪽에 있는 노드부터 제거   
        
        
        for x in bfs_graph[node]:       
            if x not in bfslist:        # 방문리스트에 포함되어 있지 않으면
                bfslist.append(x)       # 방문리스트에 포함
                queue.append(x)        

    return bfslist

DFS(Depth-First Search) - 깊이우선탐색

• 최대한 깊게 들어가면서 탐색. 스택 (LIFO/후입선출) 과 재귀 함수를 이용해 구현
• 장점
  • 최선의 경우에는 가장 빠른 알고리즘임
• 단점
  • 최단경로를 찾지 못하고 시간이 오래걸릴 수 있다
  • 찾은 답이 최적이 아닐수도 있다
• 순서: 1→2→4→5→3