[알고리즘 코테] 그래프 이론

다양한 그래프 자료구조

• 그래프와 트리의 차이

	그래프	트리
방향성	방향 그래프 또는 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드 간 관계성	부모나 자식 관계 없음	부모와 자식 관계 있음
모델의 종류	네트워크 모델	계층 모델

트리는 그래프의 일종이나, 순환구조가 없어야 함.

 

• 서로소 집합(Union-Find)

공통 원소가 없는 두 집합

Union(a, b) : a가 들어있는 그룹과 b가 들어있는 그룹을 합침.

Find(a) : a가 들어있는 그룹의 ID값을 리턴함.

-> 노드들이 같은 그룹에 있는지, 그래프에 순환구조가 있는지 판단하는 용도로 사용함.

 

• 신장 트리(Spanning Tree) : 최소 연결 부분 그래프

최소 연결이란, 간선의 수가 가장 적은 것을 의미함.

n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개임.

-> 하나의 그래프에 많은 신장 트리가 존재할수도 있음.

• 최소신장트리 MST(Minimum Spanning Tree)

모든 노드를 포함(연결)하면서 사이클이 존재하지 않는 부분 그래프인 신장 트리 중에서도 사용된 간선들의 가중치 합이 최소인 트리

 

• MST 구현 방법

1) 크루스칼 알고리즘

greedy method를 이용해 네트워크의 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 알고리즘

거리가 가장 짧은 간선부터 포함키며 이때, 사이클이 생기면 건너뜀.

# Union, Find 구현
def find_parent(parent, x) :
    if parent[x] != x :
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b) :
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b

input = sys.stdin.readline
v, e = map(int, input().split())
parent = [0] * (v + 1)
 
for i in range(1, v + 1):
    parent[i] = i
 
edges = []
result = 0
 
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((a, b, cost))
    
# Kruskal 알고리즘
def kruskal(edges, parent) :
 
    edges.sort(key=lambda x: x[2])
    mst = []

    for edge in edges :
        weight, a, b = edge
        if find_parent(parent, a) != find_parent(parent, b) :
            union_parent(parent, a, b)
            mst.append(edge)

    return mst
    
kruskal(edges, parent)

 

2) 프림 알고리즘

시작 정점으로 노드 하나를 잡고 연결되어 있는 간선 중 가장 짧은 것을 추가해나가면서 단계적으로 확장하는 알고리즘

이때, 사이클이 생기면 건너뜀.

import heapq
import collections
import sys

n, m = map(int,input().split()) # 노드 수, 간선 수
graph = collections.defaultdict(list) # 빈 그래프 생성
visited = [0] * (n+1) # 노드의 방문 정보 초기화

# 무방향 그래프 생성
for i in range(m): # 간성 정보 입력 받기
    u, v, weight = map(int,input().split())
    graph[u].append([weight, u, v])
    graph[v].append([weight, v, u])


# 프림 알고리즘
def prim(graph, start_node):
    visited[start_node] = 1 # 방문 갱신
    candidate = graph[start_node] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성
    mst = [] 
    total_weight = 0 # 전체 가중치

    while candidate :
        weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
        if visited[v] == 0 : 
            visited[v] = 1 
            mst.append((u,v)) 
            total_weight += weight # 전체 가중치 갱신

            for edge in graph[v] : # 다음 인접 간선 탐색
                if visited[edge[2]] == 0 : # 방문한 노드가 아니라면, (순환 방지)
                    heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입

    return total_weight