[알고리즘] Week 11: 그래프 알고리즘 II - 최단 경로 알고리즘과 최소 스패닝 트리

Day 1: 최단 경로 알고리즘 개요

• 강의 내용:
  • 최단 경로 문제 정의
    • 최단 경로 문제란 무엇인가?
    • 단일 출발점 최단 경로와 모든 쌍 최단 경로 문제의 차이
  • 최단 경로 알고리즘의 응용 사례
    • 네비게이션 시스템
    • 네트워크 라우팅
• 실습:
  • 최단 경로 문제를 해결할 기본적인 그래프 준비

# 기본적인 그래프 준비
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

 

Day 2: 다익스트라 알고리즘 (Dijkstra's Algorithm)

• 강의 내용:
  • 다익스트라 알고리즘의 개념
    • 다익스트라 알고리즘의 정의 및 작동 원리
    • 우선순위 큐를 이용한 구현
  • 다익스트라 알고리즘의 시간 복잡도
    • 힙을 사용한 구현의 시간 복잡도 (O((V + E) log V))
• 실습:
  • 파이썬을 사용한 다익스트라 알고리즘 구현 및 예제

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 예제 실행
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print("다익스트라 알고리즘 결과:", dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

 

Day 3: 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

• 강의 내용:
  • 벨만-포드 알고리즘의 개념
    • 벨만-포드 알고리즘의 정의 및 작동 원리
    • 음의 가중치를 허용하는 최단 경로 알고리즘
  • 벨만-포드 알고리즘의 시간 복잡도
    • 시간 복잡도 (O(VE))
• 실습:
  • 파이썬을 사용한 벨만-포드 알고리즘 구현 및 예제

def bellman_ford(graph, start):
    distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distance[vertex] + weight < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + weight

    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distance[vertex] + weight < distance[neighbor]:
                return "Graph contains a negative-weight cycle"

    return distance

# 예제 실행
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print("벨만-포드 알고리즘 결과:", bellman_ford(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

 

Day 4: 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

• 강의 내용:
  • 플로이드-워셜 알고리즘의 개념
    • 플로이드-워셜 알고리즘의 정의 및 작동 원리
    • 모든 쌍 최단 경로 알고리즘
  • 플로이드-워셜 알고리즘의 시간 복잡도
    • 시간 복잡도 (O(V^3))
• 실습:
  • 파이썬을 사용한 플로이드-워셜 알고리즘 구현 및 예제

def floyd_warshall(graph):
    dist = {i: {j: float('inf') for j in graph} for i in graph}
    for vertex in graph:
        dist[vertex][vertex] = 0
        for neighbor in graph[vertex]:
            dist[vertex][neighbor] = graph[vertex][neighbor]

    for k in graph:
        for i in graph:
            for j in graph:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 예제 실행
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print("플로이드-워셜 알고리즘 결과:", floyd_warshall(graph))
# {
# 'A': {'A': 0, 'B': 1, 'C': 3, 'D': 4},
# 'B': {'A': 1, 'B': 0, 'C': 2, 'D': 3},
# 'C': {'A': 3, 'B': 2, 'C': 0, 'D': 1},
# 'D': {'A': 4, 'B': 3, 'C': 1, 'D': 0}
# }

 

Day 5: 최소 스패닝 트리 개요

• 강의 내용:
  • 최소 스패닝 트리의 개념
    • 최소 스패닝 트리(MST)란 무엇인가?
    • MST의 중요성 및 응용 사례
• 실습:
  • MST 문제를 해결할 기본적인 그래프 준비

# 기본적인 그래프 준비
graph = {
    0: {1: 10, 2: 6, 3: 5},
    1: {0: 10, 3: 15},
    2: {0: 6, 3: 4},
    3: {0: 5, 1: 15, 2: 4}
}

 

Day 6: 크루스칼 알고리즘 (Kruskal's Algorithm)

• 강의 내용:
  • 크루스칼 알고리즘의 개념
    • 크루스칼 알고리즘의 정의 및 작동 원리
    • 간선 선택 기준 (가장 가중치가 작은 간선 선택)
    • 유니온-파인드 자료구조 사용
  • 크루스칼 알고리즘의 시간 복잡도
    • 힙을 사용한 구현의 시간 복잡도 (O(E log E))
• 실습:
  • 파이썬을 사용한 크루스칼 알고리즘 구현 및 예제

# 크루스칼 알고리즘 구현
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    def kruskal_mst(self):
        result = []
        i = e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 예제 실행
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print("크루스칼 알고리즘에 의한 최소 스패닝 트리:", g.kruskal_mst())  # [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

 

Day 7: 프림 알고리즘 (Prim's Algorithm)

• 강의 내용:
  • 프림 알고리즘의 개념
    • 프림 알고리즘의 정의 및 작동 원리
    • 시작 노드에서부터 신장 트리를 확장하는 그리디 전략
  • 프림 알고리즘의 시간 복잡도
    • 힙을 사용한 구현의 시간 복잡도 (O(E log V))
• 실습:
  • 파이썬을 사용한 프림 알고리즘 구현 및 예제

# 프림 알고리즘 구현
import heapq

def prim_mst(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start)]
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        mst.append((u, weight))
        
        for v, w in graph[u].items():
            if v not in visited:
                heapq.heappush(min_heap, (w, v))
    
    return mst

# 예제 실행
graph = {
    0: {1: 10, 2: 6, 3: 5},
    1: {0: 10, 3: 15},
    2: {0: 6, 3: 4},
    3: {0: 5, 1: 15, 2: 4}
}
print("프림 알고리즘에 의한 최소 스패닝 트리:", prim_mst(graph, 0))  # [(0, 0), (3, 5), (2, 4), (1, 10)]

 

이 강의는 파이썬의 그래프 알고리즘, 특히 최단 경로 알고리즘과 최소 스패닝 트리의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!