그래프 알고리즘

그래프

그래프의 속성

• 정점($V$, vertex)
• 간선($E$, edge)
  • 방향
  • 가중치

그래프의 표현

그래프의 속성과 목적에 따라
인접 리스트 표현과 인접 행렬 표현 중
더 효율적인 그래프 표현을 선택할 수 있다.

인접 리스트 표현법

• 낮은 밀도 : $|E|$ 값이 $|V^2|$ 보다 훨씬 작은 그래프

필요한 메모리의 양 : $O(V + E)$

인접 리스트 길이의 총 합

• 방향 그래프 : $|E|$
• 무방향 그래프 : $2|E|$

인접 행렬 표현법

• 높은 밀도 : $|E|$ 값이 $|V^2|$ 와 거의 비슷한 그래프
• 두 정점을 연결하는 간선의 존재 여부만 확인 할 경우

필요한 메모리의 양 : $O(V^2)$

무방향 그래프에서는 행렬의 주 대각선을 따라 대칭으로 나타나므로
메모리를 절반 정도로 줄일 수 있음

또한 가중치가 없는 그래프에서 각 행렬 원소마다 한 비트(bit)만으로 표현 가능

강한 연결 요소

유향 그래프에서,
모든 정점에 대해서 모든 정점이 서로 도달 가능할 때
해당 그래프를 강하게 연결되었다고 한다.

또한, 강하게 연결된 그래프가 아니더라도
그래프 내의 두 정점이 서로 도달 가능하다면
두 정점은 강한 연결 요소 이다.

출처 : 위키피디아 - 강한 연결 요소

최소 신장 트리(MST)

최소 신장 트리는 '최소 가중치 신장 트리'라는 말의 단축형으로,
무방향 그래프의 모든 정점을 최소한의 가중치로 연결하는 트리이다.

크루스칼 알고리즘

Disjoint Set(서로소 집합)을 구현한 Union-Find를 이용하여

정점을 포함하는 트리의 root를 찾고(Find),
root가 서로 다른 각각의 정점이 포함된 두 트리를 합치며(Union)

각 단계에서 두 정점을 항상 최소 가중치의 경로로 연결하는 그리디 알고리즘

프림 알고리즘

min-heap을 이용해 가중치가 가장 낮은 간선을 연결하고,
새로 연결된 정점에서 추가되는 연결될 수 있는 새로운 간선을 heap에 추가하며

모든 연결되지 않은 정점에 대한 연결 가능한 간선 중
항상 가중치가 낮은 간선을 연결하는 그리디 알고리즘

연관 문제

문제 : BOJ 1197 최소 스패닝 트리

주어지는 두 정점과 간선의 가중치를 이용해서
만들 수 있는 최소 신장 트리(MST)의 간선 가중치 합을 구하는 문제

[ 코드 : 크루스칼 알고리즘 ]

import sys

# Edge: 간선을 이루는 두 정점과 가중치를 가지는 class
class Edge:
    # 초기화 메서드(생성자). 매개변수는 순서대로 정점1, 정점2, 가중치
    def __init__(self, n1, n2, cost):
        self.n1 = n1
        self.n2 = n2
        self.cost = cost

    # (less then). 객체간 비교를 위한 메서드. 가중치의 오름차순으로 객체를 정렬하기 위해 사용
    def __lt__(self, other):
        return self.cost < other.cost

    def __str__(self) -> str:
        return 'n1: {}, n2: {}, cost: {}'.format(self.n1, self.n2, self.cost)


# union(): 두 노드를 각각 포함하는 트리를 합쳐준다.
# 두 트리가 합쳐지면 두 정점 사이의 이동 가능한 경로가 존재함
def union(a, b):
    a = find(a)
    b = find(b)
    # a, b의 root가 같으면 합칠 필요 없음
    if a == b:
        return

    # a, b의 root가 다른 경우, 트리의 높이(rank)가 더 낮은 트리를 높은 트리 밑에 넣는다.
    if rank[a] < rank[b]:
        parent[a] = b
    else:
        parent[b] = a

    if rank[a] == rank[b]:
        rank[a] += 1


# find(): 노드를 포함하는 트리의 root 노드를 찾는다.
def find(x):
    # 자기 자신이 root 노드일 경우 그대로 return
    if x == parent[x]:
        return x
    # 그 외의 경우 재귀 호출을 통해 부모노드의 부모를 찾는다.
    else:
        # 이때, 찾은 x가 속한 트리의 root 노드를 x의 부모 노드로 바로 연결시켜주며 트리를 압축한다.
        parent[x] = find(parent[x])
        return parent[x]


v, e = map(int, sys.stdin.readline().split())
edges = []

for _ in range(e):
    n1, n2, cost = map(int, sys.stdin.readline().split())
    edges.append(Edge(n1, n2, cost))

# parent : index의 부모노드를 저장하는 리스트
# 처음에 각 노드 자기 자신을 root로 초기화
parent = [i for i in range(v+1)]

# rank: index의 트리 길이를 저장하는 리스트
# 트리의 길이를 비교해서 효율적으로 압축하기위해 사용한다.
# 자신이 root인 각 노드의 길이는 0
rank = [0] * (v+1)

# 입력받은 간선을 가중치의 가중치가 감소하지 않는 순서(오름차순)으로 순회하기 위해 정렬한다
edges.sort()

total = 0   # 최소 비용을 저장할 변수
for edge in edges:
    # 두 정점의 root가 같지 않을 경우에만 union()을 진행하며 cost를 계산해준다.
    # 그 이유는 순회 순서가 가중치의 오름차순 이므로, 두 정점이 사이의 경로가 존재하는 상태 인 경우, 이미 최소 비용으로 연결 되어있기 때문.
    if find(edge.n1) != find(edge.n2):
        union(edge.n1, edge.n2)
        total += edge.cost

print(f'{total}')

[ 코드 : 프림 알고리즘 ]

import sys, heapq


class Edge:
    def __init__(self, dest, cost):
        self.dest = dest
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

    def __str__(self):
        return f'dest: {self.dest}, cost: {self.cost}'


INF = 9999999999999

v, e = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(v+1)]
for _ in range(e):
    n1, n2, cost = map(int, sys.stdin.readline().split())
    edges[n1].append(Edge(n2, cost))
    edges[n2].append(Edge(n1, cost))


def add_edge(queue, vertex):
    for e in edges[vertex]:
        heapq.heappush(queue, e)
    
    
def prim(root):
    global INF

    total_cost = 0          # MST의 가중치 합을 저장할 변수

    visited = [0] * (v+1)   # 정점이 연결되었는지 여부를 체크해줄 리스트
    queue = []              # 간선의 가중치를 key로 하는 min_heap으로 이용할 리스트

    # 최초 시작 위치(root)는 가중치가 0인 간선으로 저장해준다.
    heapq.heappush(queue, Edge(root, 0))

    # 모든 정점의 수 만큼 반복한다.
    for _ in range(v):
        cur_node = -1
        min_cost = INF
        while queue:
            tmp = heapq.heappop(queue)
            cur_node = tmp.dest
            if visited[cur_node] == 0:
                min_cost = tmp.cost
                break

        # 모든 정점의 수-1 만큼 간선을 연결하기 전에 최소 비용이 갱신되지 않았다는 뜻은
        # queue가 가지고 있는 간선으로, 연결할 수 있는 새로운 정점이 더 이상 존재하지 않는다는 이야기이며,
        # 이는 곧 그래프 내의 모든 정점이 서로 '도달 가능한 상태'가 될 수 없음을 의미한다.
        # 따라서 최소 신장 트리(MST)를 만들 수 없기 때문에, 조건에서 가중치의 합으로 나올 수 없는 수를 return 시켜준다.
        if min_cost == INF:
            return INF

        # 현재 연결한 간선의 가중치값을 더해줌
        total_cost += min_cost

        # 현재 순회에서 방문한 정점에 대한 방문 체크
        visited[cur_node] = 1

        # 현재 순회에서 방문한 정점으로 연결할 수 있는 새로운 간선을 queue에 담아온다.
        add_edge(queue, cur_node)
        
    return total_cost


print(prim(1))