Chapter 18. 그래프로 뭐든지 연결하기

Chapter 18. 그래프로 뭐든지 연결하기

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 그래프
        1-1. 그래프 대 트리
        1-2. 그래프 용어
        1-3. 기초 그래프 구현
        1-4. 방향 그래프 (Directed graph)
        1-5. 객체 지향 그래프 구현
2. 그래프 탐색
        2-1. 깊이 우선 탐색 (Depth-First Search, DFS)
        2-2. 너비 우선 탐색 (Breadth-First Search, BFS)
        2-3. 깊이 우선 탐색 vs 너비 우선 탐색
3. 가중 그래프
4. 최단 경로 문제
        4-1. 데이크스트라의 알고리즘 (p442)
5. 연습 문제 정리

• 그래프(graph)는 관계에 특화된 자료 구조이다. 데이터가 서로 어떻게 연결되어 있는지 쉽게 나타낼 수 있다.

1. 그래프

1-1. 그래프 대 트리

• 트리는 그래프의 한 종류이다.
• 트리에는 사이클(cycle)이 존재하지 않는다.
  • 사이클이란 순환적으로 참조하는 노드가 있는 것을 의미한다.
  • 쉽게 이야기하면 자기 자신으로 돌아오는 경로가 있는 그래프이다.
• 트리는 모든 노드가 서로 연결되어 있어야 한다.
• 종합하면 그래프가 트리의 상위 개념이다. (혹은 트리는 그래프에 속하는 하위 개념이다).

 

1-2. 그래프 용어

• 그래프에서는 각 노드를 정점(vertex)라 부른다.
• 정점(vertex)를 연결하는 선을 간선(edge)라 부른다.
• 간선(edge)으로 서로 연결된 두 노드는 서로 인접하다(adjacent)고 한다. 혹은 이웃(neighbor)이라고도 한다.
• 모든 정점(vertex)이 어떤 식으로든 서로 연결된 그래프를 연결 그래프(connected graph)라 한다.

 

1-3. 기초 그래프 구현

• 코드 구현 (python)
  • 파이썬으로 변환하며 딕셔너리(해시 테이블)를 사용한다.
  • 해시 테이블을 사용하기에 각 인물("Alice", "Bob", "Cynthia", "Diana", "Elise", "Fred")의 친구를 $O(1)$만에 찾을 수 있다.
    • 해시 테이블의 룩업은 $O(1)$이다.

friends = {
    "Alice": ["Bob", "Diana", "Fred"],
    "Bob": ["Alice", "Cynthia", "Diana"],
    "Cynthia": ["Bob"],
    "Diana": ["Alice", "Bob", "Fred"],
    "Elise": ["Fred"],
    "Fred": ["Alice", "Diana", "Elise"]
}

 

 

1-4. 방향 그래프

• 방향 그래프(directed graph)란 하나의 vertex에서 다른 vertex로 화살표로 연결된 그래프를 의미한다.
  • 서로 상호적으로 연결된 그래프가 아니다.
  • 화살표는 관계의 방향(direction)을 의미한다.
• 코드 구현
  • 일반적인 그래프와는 다르게 서로가 key-value로 연결되어 있지 않다.
  • e.g. "Alice"에는 "Bob"이 value로 포함되지만 "Bob"에는 "Alice"가 value로 포함되지 않는다. 따라서 'Alice → Bob' 형태의 그래프이다.

followees = {
    "Alice" : ["Bob", "Cynthia"],
    "Bob" : ["Cynthia"],
    "Cynthia" : ["Bob"]
}

 

 

1-5. 객체 지향 그래프 구현

• 방향 그래프 구현

# 방향 그래프 구현---------------------------------------------------
class Vertex:
    def __init__(self, value):
		    # value는 각 vertex를 의미한다.
        self.value = value
        # adjacent_vertices는 하나의 vertex와 인접한
        # 모든 vertex들의 배열이다.
        self.adjacent_vertices = []
        
    def add_adjacent_vertex(self, vertex):
        self.adjacent_vertices.append(vertex)

# 그래프 생성---------------------------------------------------------     
alice = Vertex("alice")
bob = Vertex("bob")
cynthia = Vertex("cynthia")

alice.add_adjacent_vertex(bob)
alice.add_adjacent_vertex(cynthia)
bob.add_adjacent_vertex(cynthia)
cynthia.add_adjacent_vertex(bob)

• 무방향 그래프(undirected graph) 구현. add_adjacent_vertex 함수를 수정한다.

def add_adjacent_vertex(self, vertex):
    # 재귀의 기저 조건이다.
    # 인접한 vertex에 존재하는 경우
    # return을 통해 수행을 종료한다.
    if vertex in self.adjacent_vertices:
        return
    # 기준 vertex에 인접한 vertex를 추가한다.
    self.adjacent_vertices.append(vertex)
    # 추가된 인접한 vertex에 기준 vertex를 추가한다.
    vertex.add_adjacent_vertex(self)

---

2. 그래프 탐색

• 그래프에서 탐색이란 다음과 같다. 탐색이란 그래프 내의 한 정점이 다른 정점과 연결되어 있을 때, 해당 정점(vertex)과 (어떤 방식으로든) 연결된 또 다른 특정 정점(vertex)을 찾는 것을 의미한다.
  • 쉽게 이야기하면 하나의 정점에서 다른 정점까지의 경로(path)를 찾는 것을 의미한다.
  • 경로(path)란 한 정점에서 다른 정점으로 가는 간선(edge)들의 순열을 의미한다.
• 교재에서는 '깊이 우선 탐색(depth-first search, DFS)'과 '너비 우선 탐색(breadth-first search, BFS)'를 다룬다.
  • 그래프 탐색에서 중요한 것은 방문했던 정점을 기록하여 재방문 시에 인지하도록 해야한다. 
  • 사이클이 있는 그래프의 경우 방문기록을 해두지 않으면 무한히 순환하는 문제가 발생한다.

 

2-1. 깊이 우선 탐색 (Depth-First Search, DFS)

• 깊이 우선 탐색은 재귀를 활용한다.
• 깊이 우선 탐색 수행
  • step 1 : 그래프 내의 임의의 정점에서 시작한다.
    
    • 시작 정점은 현재 정점이 된다.
  • step 2 : 현재 정점을 해시 테이블에 추가한다.
    • 해시 테이블에 추가함으로서 방문했던 정점임을 기록한다.
  • step 3 : 현재 정점의 인접 정점 중 하나로 방문한다..
    
    • 방문 O : 무시한다.
    • 방문 X : 해당 정점을 현재 정점으로 한다. 그리고 재귀를 통해 깊이 우선 탐색을 지속한다.
  • step 5 : 모든 정점을 방문할 때까지 반복한다.
• p414를 통해 구체적으로 이해할 수 있다.
• 코드 구현 (DFS)

def dfs_traverse(vertex, visited_vertices=None):
    # 기본적으로 방문한 정점을 저장할 딕셔너리를 초기화한다.
    if visited_vertices is None:
        visited_vertices = {}

    # 정점을 딕셔너리에 추가해 방문했다고 표시한다.
    # key로 정점을 기록하며 value에는 True를 할당한다.
    # True는 임시적인 값일뿐 아무런 의미를 갖지 않는다.
    visited_vertices[vertex.value] = True
    
    # 정점의 값을 출력해 제대로 순회하는지 확인한다.
    print(vertex.value)
    
    # 현재 정점의 인접 정점을 순회한다.
    for adjacent_vertex in vertex.adjacent_vertices:
    
        # 이미 방문했던 인접 정점은 무시한다.
        if adjacent_vertex.value in visited_vertices:
            # continue는 조건을 만족하면
            # 반복문을 수행하지 않고 다음 반복으로 넘어간다.
            # 여기서는 방문한 정점의 경우 반복을 수행하지 않는 조건문의 역할이다.
            continue
        
        # 인접 정점에 대해 메서드를 재귀적으로 호출한다.
        dfs_traverse(adjacent_vertex, visited_vertices)

• 특정 정점을 찾는 경우의 코드

def dfs(vertex, search_value, visited_vertices=None):
    # 기본적으로 방문한 정점을 저장할 딕셔너리를 초기화한다.
    if visited_vertices is None:
        visited_vertices = {}

    # 찾고 있던 정점이면 원래의 vertex를 반환한다.
    if vertex.value == search_value:
        return vertex

    visited_vertices[vertex.value] = True
    
    for adjacent_vertex in vertex.adjacent_vertices:
        if adjacent_vertex.value in visited_vertices:
            continue
        
        # 인접 정점이 찾고 있던 정점이면
        # 찾고 있던 정점을 계속 찾는다.
        vertex_were_searching_for = dfs(adjacent_vertex, search_value, visited_vertices)
        
        # 위 재귀에서 올바른 정점을 찾았다면
        # 그 정점을 반환한다.
        if vertex_were_searching_for:
            return vertex_were_searching_for
    
    # 찾고 있던 정점을 찾지 못했으면
    return None

 

 

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

• 너비 우선 탐색은 큐를 사용한다. 깊이 우선 탐색이 재귀를 사용하는 것과는 다르다.
• 너비 우선 탐색 수행
  • step 1 : 그래프 내의 임의의 정점에서 시작한다.
    • 해당 정점은 시작 정점이 된다.
  • step 2 : 시작 정점을 해시 테이블에 추가한다.
    • 방문했음을 기록하는 것이다.
  • step 3 : 시작 정점을 큐에 추가한다. 이제 큐가 빌 때까지 루프를 시작한다.
    • loop 1 : 큐 안에서 첫 번째 정점을 삭제한다.
      • 삭제된 정점이 현재 정점이 된다.
    • loop 2 : 현재 정점을 기준으로 인접 정점을 순회한다.
      • 방문 O : 무시한다.
      • 방문 X : 해시 테이블과 큐에 해당 정점을 추가한다.
    • loop 3 : 모든 정점을 방문한 경우 큐의 첫 번째 정점을 삭제한다.
      • 삭제된 정점이 현재 정점이 된다.
      • 현재 정점이 변경 되었으므로 인접 정점 순회를 시작한다.
  • step 4 : 큐가 빌 때까지 반복한다.
    • 큐가 비었을 때가 모든 정점을 방문한 시점이다.
• 코드 구현 (BFS)

def bfs_traverse(starting_vertex):
    queue = Queue()  # Queue 클래스를 사용한다고 가정합니다.
    
    visited_vertices = {}
    visited_vertices[starting_vertex.value] = True
    queue.enqueue(starting_vertex)
    
    # 큐가 빌 때까지 실행한다.
    while queue.read():
        # 큐에서 첫 번째 정점을 삭제해 현재 정점으로 만든다.
        current_vertex = queue.dequeue()
        
        # 현재 정점의 값을 출력한다.
        print(current_vertex.value)
        
        # 현재 정점의 인접 정점을 순회한다.
        for adjacent_vertex in current_vertex.adjacent_vertices:
            # 아직 방문하지 않은 인접 정점이면
            if adjacent_vertex.value not in visited_vertices:
                # 그 인접 정점에 방문했다고 표시한다.
                visited_vertices[adjacent_vertex.value] = True
                
                # 그 인접 정점을 큐에 추가한다.
                queue.enqueue(adjacent_vertex)

 

 

2-3. 깊이 우선 탐색 vs 너비 우선 탐색

• 깊이 우선 탐색은 현재 정점을 기준으로 가장 먼 정점까지 탐색을 반복한다. 반면 너비 우선 탐색은 현재 정점을 기준으로 인접한 정점을 먼저 탐색한다.
  • 깊이 우선 탐색은 가계도 등을 탐색할 때 효율적이다. 가계도는 조상부터 자손까지 수직적으로 탐색하는 경우가 많기 때문이다.
  • 너비 우선 탐색은 친구를 탐색하는 데 효율적이다. 특정 인물의 인접 정점부터 탐색하기에 바로 이웃한 친구를 탐색할 수 있다.
• 최악의 경우 깊이 우선 탐색과 너비 우선 탐색 모두 전체 그래프를 순회해야하기에 시간 복잡도가 동일하다. 그러나 탐색 방법이 다르기에 문제에 따라 효율성이 다라진다.

 

2-4. 그래프 탐색의 효율성

• 깊이 우선 탐색과 너비 우선 탐색 모두 최악의 경우 모든 정점을 순회한다.
• 깊이 우선 탐색과 너비 우선 탐색은 시간 복잡도를 계산할 때 정점의 수 뿐만아니라 인접 정점의 수(그러니까 간선(edge)의 수)까지 고려해야 한다.
• 두 탐색의 시간 복잡도는 $O(V + E)$이다.
  • $V$ : Vertex의 수
  • $E$ : Edge의 수
• 정확히는 $V+2E$의 단계가 필요하다.
  • 개별 정점을 모두 순회하면 간선은 두 번씩 count되기 때문이다.
• 번외로 그래프는 데이터를 처리하는데 효울적이기 때문에 그래프를 기반으로한 그래프 데이터베이스도 존재한다.

---

3. 가중 그래프

• 가중 그래프(weighted graph)는 간선(edge)에 정보를 추가하여 생성한 그래프이다.
  • 도시를 정점으로하고, 각 도시간의 거리 정보를 간선에 포함한다.
  • 공항을 정점으로하고, 각 비행기 경로의 가격 정보를 간선에 포함한다.
• 코드 구현

class WeightedGraphVertex:
    def __init__(self, value):
        self.value = value
        # 해시 테이블로 값을 저장한다.
        self.adjacent_vertices = {}
    
    # 해시 테이블의 key에는 정점을
    # value에는 간선(edge)의 정보를 저장한다.
    def add_adjacent_vertex(self, vertex, weight):
        self.adjacent_vertices[vertex] = weight
        
# 테스트 코드
dallas = WeightedGraphVertex("Dallas")
toronto = WeightedGraphVertex("Toronto")

dallas.add_adjacent_vertex(toronto, 138)
toronto.add_adjacent_vertex(dallas, 216)

---

4. 최단 경로 문제

• 하나의 정점에서 다른 정점으로 가는 최소한의 비용이 드는 경로를 찾는 문제를 최단 경로 문제(shortest path problem)라 한다.
  • 하나의 공항에서 다른 공항까지로 가는 최단 경로 문제 등.

 

4-1. 데이크스트라의 알고리즘 (p442)

• 데이크스트라 알고리즘을 사용하면 특정 정점에서 다른 모든 정점으로의 최단 경로를 찾을 수 있다.
• 데이크스트라 알고리즘을 수행할 때에는 두 개의 해시 테이블을 사용한다.
  • 최소 비용을 기록하는 해시 테이블
  • 직전 정점을 기록하는 해시 테이블
• 데이크스트라 알고리즘 수행
  • step 1 : 임의의 정점을 시작 정점으로 시작한다.
    • 시작 정점은 "현재 정점"이 된다.
  • step 2 : 현재 정점에서 각 인접 정점으로의 비용을 확인한다.
  • step 3 : 
    • 더 적은 비용의 경로가 있는 경우 : 기존 비용을 더 적은 비용으로 업데이트한다.
    • 더 적은 비용의 경로가 없는 경우 : 그대로 유지한다.
    • 인접 정점이 없는 경우 : 인접 정접을 key로, 현재 정점을 value로 하여 해시 테이블을 업데이트한다.'
  • step 4 : 현재 정점을 방문하지 않은 정점이면서 시작 정점과 최소 비용으로 인접한 정점으로 변경한다.
  • step 5 : 모든 정점을 방문할 때까지 반복한다.
• 데이크스트라 알고리즘을 완료하면 다음 두 가지를 알 수 있다.
  • 각 정점으로의 최소 비용.
  • 각 정점으로 가는 최단 경로 (최소 비용에 해당하는).
• 코드 구현
  • 배열로 구현한 데이크스트라 알고리즘은 최대 $O(V^2)$ 단계가 걸린다. ($V$ = 정점의 수).
    • 각 정점이 그래프 내의 다른 모든 정점으로 이루어지는 간선을 하나씩 포함하기 때문이다.
    • 따라서 각 정점마다 모든 정점에서 다른 정점으로 이어지는 경로의 가중치를 확인한다.
  • 우선순위 큐로 구현할 경우 훨씬 빨라진다. (코드의 간편성을 유지하기 위해 배열 사용).
  • 데이크스트라 알고리즘은 그래프를 탐색하며 최단 경로를 찾는 데 집중한 알고리즘이다.

class City:
    def __init__(self, name):
        self.name = name
        self.routes = {}

    def add_route(self, city, price):
        self.routes[city] = price

# 데이크스트라 알고리즘 구현==========================================================================        
def dijkstra_shortest_path(starting_city, final_destination): # 인수로 두 정점을 받는다.
    # 알고리즘이 수행되게 하는 두 개의 해시 테이블을 생성한다.
    # 하나는 최단 경로 비용, 다른 하나는 직전 정점 기록.
    cheapest_prices_table = {}
    cheapest_previous_stopover_city_table = {}
    
    # 아직 방문하지 않은 알려진 도시를 리스트에 기록한다.
    # 가장 저렴한 정점을 방문하기에 우선순위 큐가 가장 접합하다.(자료구조 = 힙)
    # 그러나 간단한 코드 구현을 위해 배열을 사용한다.
    unvisited_cities = []
    
    # 방문했던 도시를 해시 테이블에 기록한다.
    # 룩업만을 수행하기에 해시 테이블을 사용한다.
    visited_cities = {}
    
    # cheapest_prices_table의 첫 번째 키로서 시작 도시의 이름을 추가
    cheapest_prices_table[starting_city.name] = 0
    
    current_city = starting_city
    
    # 방문하지 않은 도시가 남아 있는 동안 실행
    while current_city:
        # visited_cities 해시에 current_city의 이름을 추가
        visited_cities[current_city.name] = True
        if current_city in unvisited_cities:
            unvisited_cities.remove(current_city)
        
        # current_city의 인접 도시를 순회
        for adjacent_city, price in current_city.routes.items():
            # 새 도시를 발견하면 unvisited_cities 리스트에 추가
            if adjacent_city not in visited_cities:
                unvisited_cities.append(adjacent_city)
            
            # CURRENT city를 마지막으로 경유하는 도시로 사용해
            # STARTING city에서 ADJACENT city로 가는 비용을 계산
            price_through_current_city = (
                cheapest_prices_table[current_city.name] + price
            )
                
            # 비용이 지금까지 알려진 비용보다 저렴하면
            if (adjacent_city.name not in cheapest_prices_table or
                    price_through_current_city < cheapest_prices_table[adjacent_city.name]):
                
                # 두 표를 업데이트
                cheapest_prices_table[adjacent_city.name] = price_through_current_city
                cheapest_previous_stopover_city_table[adjacent_city.name] = current_city.name
        
        # 방문하지 않은 다음 도시를 선택
        if unvisited_cities:
            # 방문하지 않은 정점이 존재한다면
            # 해당 정점(min())을 현재 정점으로 하여 반복을 수행한다.
            current_city = min(unvisited_cities, key=lambda city: cheapest_prices_table.get(city.name, float('inf')))
        # 방문하지 않은 정점이 없다면 
        # None을 반환하고 종료한다.
        else:
            current_city = None

    # 최단 경로를 구성하려면 final destination에서부터 거슬러 올라감
    shortest_path = []
    current_city_name = final_destination.name
    
    while current_city_name != starting_city.name:
        shortest_path.append(current_city_name)
        # 이전 정점으로 현재 정점을 업데이트하고 반복을 진행한다.
        current_city_name = cheapest_previous_stopover_city_table[current_city_name]
    
    # 마지막으로 starting city를 shortest path에 추가
    shortest_path.append(starting_city.name)
    
    # 시작부터 끝까지 순서대로 경로를 나타내기 위해 출력을 뒤집음
    # [::-1]은 리스트나 문자열을 역순으로 뒤집는 슬라이스 구문.
    return shortest_path[::-1]

# 예제 구성을 위한 코드 작성==========================================================================        
atlanta = City("Atlanta")
boston = City("Boston")
chicago = City("Chicago")
denver = City("Denver")
el_paso = City("El Paso")

atlanta.add_route(boston, 100)
atlanta.add_route(denver, 160)
boston.add_route(chicago, 120)
boston.add_route(denver, 180)
chicago.add_route(el_paso, 80)
denver.add_route(chicago, 40)
denver.add_route(el_paso, 140)

dijkstra_shortest_path(atlanta, chicago)

---

5. 연습 문제 정리

4 번

# deque는 큐를 구현하는 역할을 한다.
from collections import deque 

def bfs(starting_vertex, search_value, visited_vertices=None):
    if visited_vertices is None:
        visited_vertices = {}
    
    # deque()를 통해 queue에 양방향 큐를 초기화
    queue = deque()
    
    # 방문한 정점을 기록하기 위해 해시테이블을 사용한다.
    # key는 정점이고, value는 임의의 값(True)이다.
    visited_vertices[starting_vertex.value] = True
    queue.append(starting_vertex)
    
    while queue:
        # 큐의 가장 앞의 값을 삭제하고
        # 현재 정점(current_vertex)로 한다.
        current_vertex = queue.popleft()
        
        # 현재 정점(current_vertex)이 찾는 값과 같다면
        # 현재 정점을 반환한다.
        if current_vertex.value == search_value:
            # 순회를 하는 도중 일치하는 정점을 찾았다면
            # return을 통해 값을 반환하고 종료한다.
            return current_vertex
        
        # 현재 정점이 찾는 값이 아닌 경우
        # 인접 정점을 순회한다.
        for adjacent_vertex in current_vertex.adjacent_vertices:
            if adjacent_vertex.value not in visited_vertices:
                visited_vertices[adjacent_vertex.value] = True
                queue.append(adjacent_vertex)

 

 

5 번

# deque는 큐를 구현하는 역할을 한다.
from collections import deque

def find_shortest_path(first_vertex, second_vertex, visited_vertices=None):
    if visited_vertices is None:
        visited_vertices = {}
    
    queue = deque()
    
    # 각 정점 바로 이전에 방문했던 정점을 기록하는 테이블
    previous_vertex_table = {}
    
    # 너비 우선 탐색을 이용한다.
    visited_vertices[first_vertex.value] = True
    queue.append(first_vertex)
    
    while queue:
        # 큐에서 첫 번째 값을 제거하고
        # 해당 값을 현재 정점(current_vertex)로 한다.
        current_vertex = queue.popleft()
        
        # 인접 노드를 순회한다.
        for adjacent_vertex in current_vertex.adjacent_vertices:
            if adjacent_vertex.value not in visited_vertices:
                visited_vertices[adjacent_vertex.value] = True
                queue.append(adjacent_vertex)
                
                # previous_vertex 표에 adjacent_vertex을 키로
                # current_vertex를 값으로 저장한다.
                previous_vertex_table[adjacent_vertex.value] = current_vertex.value
    
    # previous_vertex_table을 사용해 최단 경로 생성
    shortest_path = []
    current_vertex_value = second_vertex.value
    
    while current_vertex_value != first_vertex.value:
        shortest_path.append(current_vertex_value)
        current_vertex_value = previous_vertex_table.get(current_vertex_value)  # None을 반환할 수 있음

    shortest_path.append(first_vertex.value)
    
    return shortest_path[::-1]  # 리스트를 뒤집어서 반환