TIL_41 : 그래프 탐색

🙄 그래프 탐색

➡ 그래프 탐색이란?

• 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것
• 각 노드를 어떤 순서로 탐색하는지에 따라 두 종류로 나뉨
  1. Breadth First Search
  2. Depth First Search

🙄 BFS (Breadth First Search)

➡ BFS 개념

• 너비 우선 탐색

➡ BFS 알고리즘

• 시작 노드를 방문 표시 후, 큐에 넣음
• 큐에 아무 노드가 없을 때까지:
  • 큐 가장 앞 노드를 꺼낸다
  • 꺼낸 노드에 인접한 노드들을 모두 보면서:
    • 처음 방문한 노드면:
      • 방문한 노드 표시를 해준다
      • 큐에 넣어준다

class StationNode:
    """지하철 역을 나타내는 역"""
    def __init__(self, station_name):
        self.station_name = station_name
        self.adjacent_stations = []
        self.visited = False

    def add_connection(self, station):
        """파라미터로 받은 역과 엣지를 만들어주는 메소드"""
        self.adjacent_stations.append(station)
        station.adjacent_stations.append(self)


from collections import deque
from subway_graph import create_station_graph

def bfs(graph, start_node):
    """시작 노드에서 bfs를 실행하는 함수"""
    queue = deque()  # 빈 큐 생성

    # 일단 모든 노드를 방문하지 않은 노드로 표시
    for station_node in graph.values():
        station_node.visited = False
    
    # 시작점 노드를 방문 표시한 후 큐에 넣어준다    
    start_node.visited = True
    queue.append(start_node)
    
    while queue:    		# 큐에 노드가 있는 동안
        a = queue.popleft()     # 큐의 가장 앞 데이터를 갖고 온다
        for adjacent_stations_of_a in a.adjacent_stations:  # 인접한 노드를 돌면서
            if adjacent_stations_of_a.visited == False:     # 방문하지 않은 노드면
                adjacent_stations_of_a.visited = True       # 방문 표시를 하고
                queue.append(adjacent_stations_of_a)        # 큐에 넣는다

➡ BFS 알고리즘 시간 복잡도

BFS 노드 전처리 : $O(V)$

• 모든 노드의 visited 변수를 False로 만들기 위해 그래프를 다 돌기 때문에 $O(V)$

큐에서 노드 넣고 빼기 : $O(V)$

• 최대 $V$개의 노드들이 큐에 들어갔다 나오기 때문에 걸리는 총 시간은 $O(V)$

인접한 노드들을 도는데 걸리는 시간 : $O(E)$

• 노드가 한 번 나올 때마다 그 노드의 인접 리스트를 돈다
• 총 엣지 수는 $E$, $E$에 비례하는 만큼 실행
• 큐에서 뺀 노드들의 인접한 노드들을 도는데 걸리는 시간 $O(E)$

👉 $O(2V + E)$

🙄 DFS (Depth First Search)

➡ DFS 개념

• 깊이 우선 탐색

➡ DFS 알고리즘

• 시작 노드를 옅은 회색 표시 후, 스택에 넣음
• 스택에 아무 노드가 없을 때까지:
  • 스택 가장 위 노드를 꺼낸다
  • 노드를 방문 (진한 회색) 표시한다
  • 인접한 노드를 모두 보면서:
    • 처음 방문하거나 스택에 없는 노드면:
      • 옆은 회색 표시를 해준다
      • 스택에 넣어준다

class StationNode:
    """지하철 역을 나타내는 역"""
    def __init__(self, station_name):
        self.station_name = station_name
        self.adjacent_stations = []
        self.visited = False

    def add_connection(self, station):
        """파라미터로 받은 역과 엣지를 만들어주는 메소드"""
        self.adjacent_stations.append(station)
        station.adjacent_stations.append(self)


from collections import deque
from subway_graph import *

def dfs(graph, start_node):
    """dfs 함수"""
    stack = deque()  # 빈 스택 생성

    # 모든 노드를 처음 보는 노드로 초기화
    for station_node in graph.values():
        station_node.visited = 0

    start_node.visited = 1
    stack.append(start_node)
    
    while stack:
        a = stack.pop()
        a.visited = 2
        for neighbors_of_a in a.adjacent_stations:
            if neighbors_of_a.visited == 0:
                neighbors_of_a.visited = 1
                stack.append(neighbors_of_a)

➡ DFS 알고리즘 시간 복잡도

DFS 노드 전처리 : $O(V)$

• 모든 노드의 visited 변수를 False로 만들기 위해 그래프를 다 돌기 때문에 $O(V)$

스택에서 노드 넣고 빼기 : $O(V)$

• 최대 $V$개의 노드들이 스택에 들어갔다 나오기 때문에 걸리는 총 시간은 $O(V)$

스택에서 뺀 노드들의 인접한 노드들을 도는데 걸리는 시간 : $O(E)$

• 노드가 한 번 나올 때마다 그 노드의 인접 리스트를 돈다
• 총 엣지 수는 $E$, $E$에 비례하는 만큼 실행
• 스택에서 뺀 노드들의 인접한 노드들을 도는데 걸리는 시간 $O(E)$

👉 $O(2V + E)$