THEWOOWON

Graph Algorithm Series

December 29, 2022 - 우원

Graph Algorithm Series

이전 장에서는 Graph Algorithm이란 무엇인지, 어떤 상황에서 사용해야 하는지에 대해 알아보겠다.

Graph 자료 구조 공략하기

Graph란?

그래프는 정점(Vertax)의 집합과 정점들을 서로 잇는 간선(Edge)의 집합으로 이루어진 자료 구조이다. 수학적으로 표현하면 그래프 G = [V, E] 형태태로 표현하고, 여기서 V는 정점의 집합, E는 간선의 집합을 의미한다.

만약에 에지가 특정 정점에서 다른 정점으로 향하는 방향성이 있다면, 방향 그래프(Directed Graph)라고 한다. 반대로 에지가 양방향으로 향한다면, 무방향 그래프(Undirected Graph)라고 한다. 추가로 에지에 가중치가 있다면, 가중치 그래프(Weighted Graph)라고 한다. 반대로 에지에 가중치가 없다면 비가중치 그래프(Unweighted Graph)라고 한다.

Node VS Vertax

노드와 정점은 같은 의미이다. 그래프에서 정점은 노드와 같은 의미이다.

Graph의 특징

그래프는 매우 유연한 자료구조이다. 트리나 연결리스트와 같은 다른 연결된 자료 구조는 그래프의 특별한 형태라고 볼 수 있다. 그래프는 객체와 객체 사이의 관계를 표현할 수 있어서 유용하다. 그래프에서 두 정점 사이에는 여러 개의 에지가 있을 수도 있고, 또한 하나의 에지에 여러개의 가중치를 부여할 수도 있다. 특정 정점에서 나온 에지가 자기 자신으로 연결되는 셀프 에지도 만들 수 있다.

Graph의 범용성

그래프는 범용성이 높은 자료 구조이다. 그렇기 때문에 많은 응용 프로그램에서 사용되고 있다. Finite State Machine, Social Network, Web Crawling, Network Routing, Shortest Path, Minimum Spanning Tree 등 다양한 응용 프로그램에서 사용된다.

기본적인 그래프 순회 문제

쉬운 예

얼마 전에 새로운 도시로 이사를 했다. 새로운 동네에서 새로운 이웃을 만나다 보니 사람들이 주변에 괜찮은 맛집을 추천해주었다. 어제 추천받은 맛집에 모두 방문해보고 싶어서 지도 앱을 꺼내 우리 집과 맛집을 지도에 표현했다. 지도에는 이미 사용할 수 있는 도로가 표시되어 있었고 나는 이를 이용해서 맛집은 정점으로 표현하고, 도로는 에지로 표현했다. 우리 집에서 시작해서 모든 식당에 방문하려고 한다. 이때, 모든 식당을 방문하는 최단 경로를 찾아보자.

spring

위와 같은 문제가 그래프 순회 문제이다. 그래프 순회 문제는 그래프를 순회하면서 모든 정점을 방문하는 문제이다.

너비 우선 탐색(BFS)

앞서 보았던 맛집 문제를 너비 우선 탐색으로 풀어보자.

spring

그래프에서 너비 우선 탐색은 시작 정점을 어떤 경계에 추가하는 것이다. 경계는 이전에 방문했던 정점들로 구성되고, 현재 경계에 인접한 정점을 반복적으로 탐색한다.

spring

우리집을 시작 정점으로 하고, 경계에 추가한다. 경계에는 우리집만 들어있고, 현재 경계에 인접한 정점은 우리집과 연결된 정점이다.

spring

이 중에서 우리집과 연결된 정점 중 아직 방문하지 않은 정점은 두 개이다. 이 두 정점을 경계에 추가한다.

spring

다음은 다시 정점과 연결된 R3, R5를 경계에 추가하고, R4, R6도 경계에 추가한다.

너비 우선 탐색(BFS) 구현하기

def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            queue.extend(graph[n])

    return visited

위의 알고리즘으로 우리집에서 시작해 모든 정점을 방문하는 순서는 우리집, R2, R1, R3, R5, R6, R4, R7이다. BFS는 일반적으로 queue를 활용해서 구현한다. 먼저 시작 정점을 queue에 추가하고, queue가 빌 때까지 다음을 반복한다. 시작점이 되는 정점을 queue에 추가하고 반복문을 돌면서 방문한 여부를 판단한다. 이 때 중요한 점은 queue의 앞에서 부터 pop을 하고 확장을 한다는 것이다. 연결된 정점을 queue에 추출 할때면 앞에서부터 조사하기 때문에 차례대로 넓이 우선으로 연결된 정점을 추가한다.

깊이 우선 탐색(DFS)

이제 위의 우리 집에서 시작해 모든 정점을 깊이 우선으로 방문하는 순서를 알아보자.

spring

시작 정점인 우리집을 방문한다.

spring

시작 정점과 연결된 R2를 방문한다. 이때 깊이 우선 탐색은 stack을 활용하거나 재귀함수를 활용하여 구현하기 때문에 하나의 정점에 연결된 마지막 레벨까지의 노드를 방문하고 다시 돌아오는 방식으로 구현한다.

spring

R2와 연결된 R3을 방문한다.

spring

해당 알고리즘으로 모든 정점을 방문하게 되면 위와 같은 순서로 접근하게 된다.

깊이 우선 탐색(DFS) 구현하기

def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack.extend(graph[n])

    return visited

프림의 최소 신장 트리 알고리즘

최소 신장 트리는 그래프에서 모든 정점을 포함하면서 사이클이 존재하지 않는 부분 그래프를 말한다. 그리고 모든 정점을 연결했을 때 가중치의 합 또한 최소가 되는 트리를 말한다. 앞서 그릳 알고리즘 시리즈에서 크루스칼의 최소 신장 트리 알고리즘을 알아보았다. 크루스칼은 최소힙을 사용해서 매순간 최소의 가중치를 가지는 정점을 추가하면서 최소 신장 트리를 구현했다. 그렇다면 프림의 최소 신장 트리 알고리즘은 어떻게 구현할까? 프림의 최소 신장 트리 알고리즘은 크루스칼의 최소 신장 트리 알고리즘과는 다르게 시작 정점을 기준으로 연결된 간선들을 우선순위 큐에 넣고 가장 가중치가 작은 간선을 선택하면서 최소 신장 트리를 구현한다.

프림의 최소 신장 트리 알고리즘은 다음과 같은 순서로 구현한다.

  1. 모든 정점의 거리 값을 무한대로 초기화한다.
  2. 시작 정점의 거리 값을 0으로 초기화한다.(왜냐하면 자기 자신과의 거리는 0이기 때문이다.)
  3. 우선순위 큐에 모든 정점을 넣는다.(우선 순위 큐는 힙)
  4. 꺼낸 정점을 MST에 추가하고 정점과 인접한 모든 정점에 대해서 거리 값이 에지 가중치보다 해당 가중치로 설정한다.
  5. 방문하지 않은 정점이 있다면 2단계로 돌아간다.

프림의 최소 신장 트리 알고리즘 파헤치기

앞서 말했던 순서를 따라서 그림으로 살펴보자.

spring

먼저 시작 정점은 1일 때, 거리는 0으로 하고 나머지 정점들 간의 거리는 무한대로 표현한다.

spring

최소힙으로부터 정점을 꺼내서 MST에 추가한다. 그리고 모든 인점 정점들 V에 대해서 만약 거리 V의 값이 현재 정점과의 에지 가중치보다 크면 V의 거리값을 에지의 가중치로 치환한다. 사진에서도 보이듯이 시작 정점 1의 인접한 정점 2와 5의 사이값은 각각 무한대로 에지의 가중치 각각 2와 3보다 크다. 그러므로 2와 5 정점의 값은 각각 2와 3으로 치환된다.(이 때 해당 정점에 안착한다고 표현한다.)

spring

방문하지 않은 정점이 있다면 2단계로 돌아간다. 방문하지 않은 정점은 거리값이 작은 2번 정점이기 때문에 2번 정점을 MST에 추가하고 2번 정점과 인접한 정점들의 거리값을 갱신한다.

spring

모든 정점들에 대해서 안착하면 최종 MST를 구할 수 있다.

import heapq

def prim(graph, start):
    mst = []
    visited = [False] * len(graph)
    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        weight, node = heapq.heappop(heap)
        if not visited[node]:
            visited[node] = True
            mst.append((weight, node))

            for n, w in graph[node]:
                if not visited[n]:
                    heapq.heappush(heap, (w, n))

    return mst

다익스트라 알고리즘

다익스트라 알고리즘은 구글 지도 또는 자동차 네비게이션 등에서 경로를 탐색할 때 사용된다. 다익스트라는 이렇게 정의할 수 있다.

주어진 그래프 G가 있고 V라는 정점의 집합, E라는 에지의 집합이 있다. 이 때 에지는 각각 가중치를 가지고 있고 시작 정점과 목적 정점이 주어질 때, 시작 정점에서 목적 정점까지의 최소 비용 경로를 찾는 알고리즘이다.

다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변경한 형태이다. 하지만 다익스트라와 프림의 알고리즘은 두 가지 차이점이 있다.

  • 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다.
  • 다익스트라 알고리즘은 목적 정점이 나타나면 죵료하지만, 프림의 알고리즘은 모든 정점을 방문해야 종료한다.

다익스트라 알고리즘 파헤치기

그림과 순서에 따라 다익스트라 알고리즘을 살펴보자.

spring

모든 정점의 거리 값은 무한대로 초기화한다. 시작 정점은 자기 자신까지의 거리가 0이므로 0으로 초기화한다. 그리고 모든 거리 값을 최소 힙에 추가한다. 최소 힙에서 정점 하나 U를 꺼낸다.(이때 최소힙에 의해 정점의 거리가 최소인 정점이 꺼내진다.) 꺼낸 정점 U가 만약에 목적 정점이면 최단 경로를 찾은 것이므로 알고리즘을 종료한다.

spring

다시 U와 인접한 모든 정점 V에 대해서 거리값이 (U의 거리값 + U와 V사이의 에지 가중치)보다 크면 V까지 다다르는 더 짧은 경로를 찾은 것으로 본다. V의 거리값을 (U의 거리값 + U와 V사이의 에지 가중치)로 갱신하면 안착했다고 표현한다.

spring

위의 그림은 2번 정점까지 안착한 그림이고, 방문하지 않은 정점이 남아 있다면 2단계로 이동한다.

spring

목적 정점 6에 도착하면 알고리즘을 종료한다.

다익스트라 알고리즘 구현

다익스트라 알고리즘을 구현해보자.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        current_distance, current_destination = heapq.heappop(queue)
        if distances[current_destination] < current_distance:
            continue

        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

    return distances
logo

우원 /

안녕하세요👏
우원입니다.
Email
Gihub
안녕하세요. 우원봇입니다.
logo