그래프 & 백트래킹

MST

• 그래프에서 최소 비용문제
  • 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  • 두 정점 사이의 최소 비용의 경로 찾기
• 신장 트리
  • n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1 개의 간선으로 이루어진 트리
• 최소 신장 트리
  • 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

Prim 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
  • 임의 정점을 하나 선택해서 시작
  • 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
  • 모든 정점이 선택될 때까지 위의 과정 반복
• 서로소인 2개의 집합 정보를 유지
  • 트리 정점들 : MST를 만들기 위해 선택된 정점들
  • 비트리 정점들 : 선택 되지 않은 정점들

import heapq as hq

def prim(start):
  heap = list()
  # 연결되어 있는 지 확인하는 리스트
  connected = [False] * (Node_cnt + 1)

  sum_w = 0

  hq.heappush(heap, (0, start))
  sum_w = 0

  print('################')
  print('MST')

  # 우선순위 큐에 데이터가 있는동안
  while heap:
    weight,v = hq.heappop(heap)
    # 뺀 노드가 그래프에 포함되어 있지 않은 경우
    if not connected[v]:
      # 그래프에 포함 처리
      connected[v] = True
      sum_w += weight
      print('Connected Nodes:', v, 'Weight:',weight)
      for i in range(1, Node_cnt + 1):
        if graph[v][i] != 0 and not connected[i]:
          hq.heappush(heap, (graph[v][i], i))
  print('Sum of weight:', sum_w)

KRUSKAL 알고리즘

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘
  • 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
  • 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
    • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
  • n-1개의 간선이 선택될 때 까지 반복

import sys


def find_parent(parent, a):
    if parent[a] != a:
        parent[a] = find_parent(parent, parent[a])
    return parent[a]


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))

edges.sort(key=lambda x: x[2])

for a, b, cost in edges:
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)

최단 경로

• 최단 경로의 정의
  • 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
• 하나의 시작 정점에서 끝 정점까지의 최단 경로
  • 다익스트라 알고리즘
    • 음의 가중치를 허용하지 않음
  • 벨만-포드 알고리즘
    • 음의 가중치 허용
• 모든 정점들에 대한 최단 경로
  • 프롤이드 워샬 알고리즘

다익스트라 알고리즘

• 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다
• 시작정점(s)에서 끝정점(t)까지의 최단 경로에 정점 x가 존재한다
• 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로 구성된다
• 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq  # 우선순위 큐 구현을 위함

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
  distances[start] = 0  # 시작 값은 0이어야 함
  queue = []
  heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작 하기 위함.

  while queue:  # 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