[자료구조] Week 9: 그래프 II - 그래프 탐색과 최단 경로 알고리즘

Day 1: 그래프 탐색 - 깊이 우선 탐색 (DFS)

• 강의 내용:
  • 깊이 우선 탐색 (DFS)의 개념과 특징
    • DFS의 정의 및 탐색 방식
    • DFS의 시간 복잡도
  • DFS의 구현
    • 재귀적 구현
    • 비재귀적 구현 (스택 사용)
• 실습:
  • DFS의 재귀적 구현 및 비재귀적 구현

# 그래프 탐색 클래스 정의
class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

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

# DFS 재귀적 구현
def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex, end=' ')
    for neighbor in graph.adj_list[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# DFS 비재귀적 구현
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            stack.extend(reversed(graph.adj_list[vertex]))

# 그래프 생성 및 DFS 예제
graph = Graph(6)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)

print("DFS 재귀적 탐색 결과:")
dfs_recursive(graph, 0)  # 0 1 3 4 5 2

print("\nDFS 비재귀적 탐색 결과:")
dfs_iterative(graph, 0)  # 0 2 4 5 1 3

 

Day 2: 그래프 탐색 - 너비 우선 탐색 (BFS)

• 강의 내용:
  • 너비 우선 탐색 (BFS)의 개념과 특징
    • BFS의 정의 및 탐색 방식
    • BFS의 시간 복잡도
  • BFS의 구현
    • 큐를 사용한 구현
• 실습:
  • BFS 구현 및 예제

# BFS 구현
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            queue.extend([neighbor for neighbor in graph.adj_list[vertex] if neighbor not in visited])

# 그래프 생성 및 BFS 예제
graph = Graph(6)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)

print("BFS 탐색 결과:")
bfs(graph, 0)  # 0 1 2 3 4 5

 

Day 3: 최단 경로 알고리즘 - 다익스트라 알고리즘

• 강의 내용:
  • 다익스트라 알고리즘의 개념과 특징
    • 다익스트라 알고리즘의 정의 및 용도
    • 다익스트라 알고리즘의 시간 복잡도
  • 다익스트라 알고리즘의 구현
    • 우선순위 큐를 사용한 구현
• 실습:
  • 다익스트라 알고리즘 구현 및 예제

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in range(graph.num_vertices)}
    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.adj_list[current_vertex]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 가중 그래프 생성 및 다익스트라 알고리즘 예제
class WeightedGraph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v, weight):
        self.adj_list[u].append((v, weight))
        self.adj_list[v].append((u, weight))  # 무방향 그래프의 경우

graph = WeightedGraph(6)
graph.add_edge(0, 1, 7)
graph.add_edge(0, 2, 9)
graph.add_edge(0, 5, 14)
graph.add_edge(1, 2, 10)
graph.add_edge(1, 3, 15)
graph.add_edge(2, 3, 11)
graph.add_edge(2, 5, 2)
graph.add_edge(3, 4, 6)
graph.add_edge(4, 5, 9)

distances = dijkstra(graph, 0)
print("다익스트라 알고리즘 결과:", distances)  # {0: 0, 1: 7, 2: 9, 3: 20, 4: 20, 5: 11}

 

Day 4: 최단 경로 알고리즘 - 벨만-포드 알고리즘

• 강의 내용:
  • 벨만-포드 알고리즘의 개념과 특징
    • 벨만-포드 알고리즘의 정의 및 용도
    • 벨만-포드 알고리즘의 시간 복잡도
    • 음수 가중치를 가진 그래프에서의 사용
  • 벨만-포드 알고리즘의 구현
• 실습:
  • 벨만-포드 알고리즘 구현 및 예제

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

    for _ in range(graph.num_vertices - 1):
        for u in range(graph.num_vertices):
            for v, weight in graph.adj_list[u]:
                if distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight

    # 음수 사이클 검출
    for u in range(graph.num_vertices):
        for v, weight in graph.adj_list[u]:
            if distances[u] + weight < distances[v]:
                return "Graph contains a negative weight cycle"

    return distances

# 가중 그래프 생성 및 벨만-포드 알고리즘 예제
graph = WeightedGraph(5)
graph.add_edge(0, 1, -1)
graph.add_edge(0, 2, 4)
graph.add_edge(1, 2, 3)
graph.add_edge(1, 3, 2)
graph.add_edge(1, 4, 2)
graph.add_edge(3, 2, 5)
graph.add_edge(3, 1, 1)
graph.add_edge(4, 3, -3)

distances = bellman_ford(graph, 0)
print("벨만-포드 알고리즘 결과:", distances)  # {0: 0, 1: -1, 2: 2, 3: -2, 4: 1}

 

Day 5: 최단 경로 알고리즘 - 플로이드-와샬 알고리즘

• 강의 내용:
  • 플로이드-와샬 알고리즘의 개념과 특징
    • 플로이드-와샬 알고리즘의 정의 및 용도
    • 플로이드-와샬 알고리즘의 시간 복잡도
    • 모든 쌍 최단 경로 문제 해결
  • 플로이드-와샬 알고리즘의 구현
• 실습:
  • 플로이드-와샬 알고리즘 구현 및 예제

def floyd_warshall(graph):
    dist = [[float('infinity')] * graph.num_vertices for _ in range(graph.num_vertices)]
    for u in range(graph.num_vertices):
        dist[u][u] = 0
        for v, weight in graph.adj_list[u]:
            dist[u][v] = weight

    for k in range(graph.num_vertices):
        for i in range(graph.num_vertices):
            for j in range(graph.num_vertices):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 가중 그래프 생성 및 플로이드-와샬 알고리즘 예제
graph = WeightedGraph(4)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 3, 10)
graph.add_edge(1, 2, 3)
graph.add_edge(2, 3, 1)

distances = floyd_warshall(graph)
print("플로이드-와샬 알고리즘 결과:")
for row in distances:
    print(row)
# Output:
# [0, 5, 8, 9]
# [inf, 0, 3, 4]
# [inf, inf, 0, 1]
# [inf, inf, inf, 0]

 

Day 6: 최단 경로 알고리즘의 응용

• 강의 내용:
  • 최단 경로 알고리즘의 실제 응용 사례
    • 네트워크 라우팅
    • 지리 정보 시스템
  • 최단 경로 알고리즘을 사용한 문제 해결
• 실습:
  • 최단 경로 알고리즘을 사용한 응용 예제

# 네트워크 라우팅 예제
class NetworkGraph(WeightedGraph):
    def __init__(self, num_routers):
        super().__init__(num_routers)

# 네트워크 그래프 생성 및 다익스트라 알고리즘 적용 예제
network = NetworkGraph(6)
network.add_edge(0, 1, 7)
network.add_edge(0, 2, 9)
network.add_edge(0, 5, 14)
network.add_edge(1, 2, 10)
network.add_edge(1, 3, 15)
network.add_edge(2, 3, 11)
network.add_edge(2, 5, 2)
network.add_edge(3, 4, 6)
network.add_edge(4, 5, 9)

distances = dijkstra(network, 0)
print("네트워크 라우팅 결과:", distances)  # {0: 0, 1: 7, 2: 9, 3: 20, 4: 20, 5: 11}

 

Day 7: 종합 연습 및 프로젝트

• 강의 내용:
  • 그래프 탐색과 최단 경로 알고리즘을 사용한 종합 연습 문제 풀이
    • 다양한 그래프 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 최단 경로 알고리즘을 활용한 간단한 프로그램 구현
    • 예: 도시 간 최단 경로 찾기
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 무방향 그래프에서 사이클 존재 여부 확인
def has_cycle_undirected(graph):
    parent = [-1] * graph.num_vertices

    def find(i):
        if parent[i] == -1:
            return i
        return find(parent[i])

    def union(x, y):
        x_set = find(x)
        y_set = find(y)
        if x_set != y_set:
            parent[x_set] = y_set

    for u in range(graph.num_vertices):
        for v in graph.adj_list[u]:
            x = find(u)
            y = find(v)
            if x == y:
                return True
            union(x, y)

    return False

# 사이클 존재 여부 확인 예제
graph = Graph(4)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(3, 0)
print("무방향 그래프에 사이클이 존재하는가?", has_cycle_undirected(graph))  # True

# 미니 프로젝트 예제: 도시 간 최단 경로 찾기
class CityGraph(WeightedGraph):
    def __init__(self, num_cities):
        super().__init__(num_cities)

    def add_route(self, city1, city2, distance):
        self.add_edge(city1, city2, distance)

# 도시 그래프 생성 및 다익스트라 알고리즘 적용 예제
city_graph = CityGraph(5)
city_graph.add_route(0, 1, 10)
city_graph.add_route(0, 3, 30)
city_graph.add_route(0, 4, 100)
city_graph.add_route(1, 2, 50)
city_graph.add_route(2, 4, 10)
city_graph.add_route(3, 2, 20)
city_graph.add_route(3, 4, 60)

distances = dijkstra(city_graph, 0)
print("도시 간 최단 경로 결과:", distances)  # {0: 0, 1: 10, 2: 50, 3: 30, 4: 60}

 

이 강의는 파이썬의 자료구조 중 그래프 탐색과 최단 경로 알고리즘을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!