그래프 탐색

1. 그래프 탐색이란?

그래프 탐색(graph search)

• 하나의 노드에서 시작하여 connected graph를 순회하는 것

그래프 탐색 종류

• BFS(Breadth First Search)
• DFS(Depth First Search)

2. BFS(Breadth First Search)

BFS

• 시작 정점에서 시작하여 너비 우선 순서로 그래프의 모든 정점을 탐색하는 그래프 통과 알고리즘
• 다음 레벨의 정점들을 탐색하기 전에 현재 레벨의 정점들을 모두 탐색한다.

BFS 알고리즘

1. 모든 노드를 방문하지 않은 노드로 표시한다.
2. 시작 노드를 방문 표시 후, 큐에 넣는다.
3. 큐 가장 앞 노드를 꺼낸다.
4. 꺼낸 노드에 인접한 노드에 접근한다.
5. 처음 방문한 노드면 방문한 노드 표시를 해주고 큐에 넣는다.
6. 꺼낸 노드에 인접한 노드를 전부 접근하기 전까지 4단계로 돌아간다.
7. 큐에 아무 노드가 없을 때까지 3단계로 돌아간다.

from collections import deque


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)


def create_station_graph(input_file):
    stations = {}

    # 일반 텍스트 파일을 여는 코드
    with open(input_file) as stations_raw_file:
        for line in stations_raw_file:  # 파일을 한 줄씩 받아온다
            previous_station = None  # 엣지를 저장하기 위한 변수
            raw_data = line.strip().split("-")

            for name in raw_data:
                station_name = name.strip()

                if station_name not in stations:
                    current_station = StationNode(station_name)
                    stations[station_name] = current_station

                else:
                    current_station = stations[station_name]

                if previous_station is not None:
                    current_station.add_connection(previous_station)

                previous_station = current_station

    return stations


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:  # 큐에 노드가 있는 동안
        current_station = queue.popleft()  # 큐의 가장 앞 데이터를 갖고 온다
        for neighbor in current_station.adjacent_stations:  # 인접한 노드를 돌면서
            if not neighbor.visited:  # 방문하지 않은 노드면
                neighbor.visited = True  # 방문 표시를 하고
                queue.append(neighbor)  # 큐에 넣는다


stations = create_station_graph("./new_stations.txt")  # stations.txt 파일로 그래프를 만든다

gangnam_station = stations["강남"]

# 강남역과 경로를 통해 연결된 모든 노드를 탐색
bfs(stations, gangnam_station)

# 강남역과 서울 지하철 역들이 연결됐는지 확인
print(stations["강동구청"].visited)
print(stations["평촌"].visited)
print(stations["송도"].visited)
print(stations["개화산"].visited)

# 강남역과 대전 지하철 역들이 연결됐는지 확인
print(stations["반석"].visited)
print(stations["지족"].visited)
print(stations["노은"].visited)
print(stations["(대전)신흥"].visited)

True
True
True
True
False
False
False
False

BFS 알고리즘 시간 복잡도 분석

1. 모든 노드를 방문하지 않은 노드로 표시한다. (BFS 노드 전처리)
   • Worst-case time complexity: O(V)
   • Best-case time complexity: O(V)
   • Average time complexity: O(V)
2. 시작 노드를 방문 표시 후, 큐에 넣는다. (O(1))
3. 큐 가장 앞 노드를 꺼낸다. (O(1))
4. 꺼낸 노드에 인접한 노드에 접근한다. (O(1))
5. 처음 방문한 노드면 방문한 노드 표시를 해주고 큐에 넣는다. (O(1))
6. 꺼낸 노드에 인접한 노드를 전부 접근하기 전까지 3단계로 돌아간다.
   • Worst-case time complexity: O(V)
   • Best-case time complexity: O(1)
   • Average time complexity: O(Eaj)
7. 큐에 아무 노드가 없을 때까지 2단계로 돌아간다.
   • Worst-case time complexity: O(V)
   • Best-case time complexity: O(1)
   • Average time complexity: O(V)

• BFS 알고리즘 시간 복잡도
  • Worst-case time complexity: O(V^2)
  • Best-case time complexity: O(1)
  • Average time complexity: O(V+E)

3. DFS(Depth First Search)

DFS

• 시작 정점에서 시작하여 backtracking하기 전에 각 분기를 따라 가능한 한 깊은 레벨까지 탐색하는 그래프 통과 알고리즘
• 다음 줄의 정점들을 탐색하기 전에 현재 줄의 모든 레벨에 있는 정점들을 모두 탐색한다.

DFS 알고리즘

• 방문한 노드에 현재 스택에 들어있는지에 대한 정보도 추가해야한다.

1. 모든 노드를 방문하지 않은 노드로 표시한다.
2. 시작 노드를 스택에 넣은 노드로 표시해주고, 스택에 넣는다.
3. 스택 가장 위 노드를 꺼내고 스택에서 꺼낸 노드로 표시한다.
4. 꺼낸 노드에 인접한 노드에 접근한다.
5. 처음 방문한 노드면 스택에 넣은 노드로 표시해주고 스택에 넣는다.
6. 꺼낸 노드에 인접한 노드를 전부 접근하기 전까지 4단계로 돌아간다.
7. 스택에 노드가 있다면 3단계로 돌아간다.

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:  # 스택에 노드가 남아 있을 때까지
        current_node = stack.pop()
        current_node.visited = 2  # 현재 노드를 스택에서 꺼낸 노드로 표시
        for neighbor in current_node.adjacent_stations:
            if neighbor.visited == 0:
                neighbor.visited = 1
                stack.append(neighbor)

DFS 알고리즘 시간 복잡도 분석

1. 모든 노드를 방문하지 않은 노드로 표시한다.
   • Worst-case time complexity: O(V)
   • Best-case time complexity: O(V)
   • Average time complexity: O(V)
2. 시작 노드를 스택에 넣은 노드로 표시해주고, 스택에 넣는다. (O(1))
3. 스택 가장 위 노드를 꺼내고 스택에서 꺼낸 노드로 표시한다. (O(1))
4. 꺼낸 노드에 인접한 노드에 접근한다. (O(1))
5. 처음 방문한 노드면 스택에 넣은 노드로 표시해주고 스택에 넣는다. (O(1))
6. 꺼낸 노드에 인접한 노드를 전부 접근하기 전까지 4단계로 돌아간다.
   • Worst-case time complexity: O(V)
   • Best-case time complexity: O(1)
   • Average time complexity: O(Eaj)
7. 스택에 노드가 있다면 3단계로 돌아간다.
   • Worst-case time complexity: O(V)
   • Best-case time complexity: O(1)
   • Average time complexity: O(V)

• BFS 알고리즘 시간 복잡도
  • Worst-case time complexity: O(V^2)
  • Best-case time complexity: O(1)
  • Average time complexity: O(V+E)

Feedback

1. BFS. DFS의 시간, 공간 복잡도를 분석해보자.
2. 언어별로 그래프 탐색을 구현해보자.
3. 추상 자료형은 그래프 탐색을 어떻게 구현했는지 찾아보자.

참고 자료

• algorithm - Breadth First Search time complexity analysis - Stack Overflow
• 그래프 - 알고리즘 · 자료구조 강의 | 코드잇