[알고리즘] Week 10: 그래프 알고리즘 I - 개념과 탐색 알고리즘

Day 1: 그래프의 개념과 용어

• 강의 내용:
  • 그래프의 정의와 중요성
    • 그래프란 무엇인가?
    • 그래프의 실생활 응용 사례 (소셜 네트워크, 지도, 인터넷 등)
  • 그래프의 기본 용어
    • 정점(Vertex)와 간선(Edge)
    • 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)
    • 가중치 그래프(Weighted Graph)와 비가중치 그래프(Unweighted Graph)
    • 인접 정점(Adjacent Vertices), 경로(Path), 차수(Degree)
  • 그래프의 종류
    • 유향 그래프와 무향 그래프
    • 연결 그래프와 비연결 그래프
    • 사이클(Cycle)과 비사이클(Acyclic)
• 실습:
  • 파이썬을 사용한 그래프의 기본 구조 생성

# 무방향 그래프의 예제 구현
class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, v):
        if v not in self.graph:
            self.graph[v] = []

    def add_edge(self, v1, v2):
        if v1 in self.graph and v2 in self.graph:
            self.graph[v1].append(v2)
            self.graph[v2].append(v1)

# 예제 실행
g = Graph()
g.add_vertex(1)
g.add_vertex(2)
g.add_vertex(3)
g.add_edge(1, 2)
g.add_edge(2, 3)
print("그래프:", g.graph)  # {1: [2], 2: [1, 3], 3: [2]}

 

Day 2: 그래프의 표현 방법

• 강의 내용:
  • 인접 행렬(Adjacency Matrix)
    • 인접 행렬의 정의 및 특징
    • 인접 행렬의 장단점
  • 인접 리스트(Adjacency List)
    • 인접 리스트의 정의 및 특징
    • 인접 리스트의 장단점
• 실습:
  • 인접 행렬과 인접 리스트를 사용한 그래프 구현

# 인접 행렬을 사용한 그래프 구현
class GraphMatrix:
    def __init__(self, size):
        self.size = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)]

    def add_edge(self, u, v):
        self.graph[u][v] = 1
        self.graph[v][u] = 1

# 인접 리스트를 사용한 그래프 구현
class GraphList:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, v):
        if v not in self.graph:
            self.graph[v] = []

    def add_edge(self, v1, v2):
        if v1 in self.graph and v2 in self.graph:
            self.graph[v1].append(v2)
            self.graph[v2].append(v1)

# 예제 실행
# 인접 행렬
gm = GraphMatrix(3)
gm.add_edge(0, 1)
gm.add_edge(1, 2)
print("인접 행렬 그래프:", gm.graph)  # [[0, 1, 0], [1, 0, 1], [0, 1, 0]]

# 인접 리스트
gl = GraphList()
gl.add_vertex(0)
gl.add_vertex(1)
gl.add_vertex(2)
gl.add_edge(0, 1)
gl.add_edge(1, 2)
print("인접 리스트 그래프:", gl.graph)  # {0: [1], 1: [0, 2], 2: [1]}

 

Day 3: 그래프 탐색 알고리즘 개요

• 강의 내용:
  • 그래프 탐색의 중요성
    • 그래프 탐색의 필요성 및 응용
    • 그래프 탐색 알고리즘의 종류
  • 너비 우선 탐색(Breadth-First Search, BFS)
    • BFS의 기본 개념과 작동 원리
    • BFS의 시간 복잡도 및 공간 복잡도
  • 깊이 우선 탐색(Depth-First Search, DFS)
    • DFS의 기본 개념과 작동 원리
    • DFS의 시간 복잡도 및 공간 복잡도
• 실습:
  • BFS와 DFS의 이론적 설명 및 간단한 예제

# 그래프 탐색 알고리즘 개요
# BFS와 DFS의 기본 예제 설명 (구현은 Day 4와 Day 5에서 다룸)

 

Day 4: 너비 우선 탐색 (Breadth-First Search, BFS)

• 강의 내용:
  • BFS 알고리즘 설명
    • BFS의 단계별 과정
    • BFS를 사용한 문제 해결 사례
  • BFS 구현
    • 큐 자료구조를 사용한 BFS 구현
• 실습:
  • 파이썬을 사용한 BFS 구현 및 예제

# BFS 알고리즘 구현
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            queue.extend(set(graph[vertex]) - visited)

    return result

# 예제 실행
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 4],
    3: [1, 4],
    4: [1, 2, 3]
}
print("BFS 결과:", bfs(graph, 0))  # [0, 1, 2, 3, 4]

 

Day 5: 깊이 우선 탐색 (Depth-First Search, DFS)

• 강의 내용:
  • DFS 알고리즘 설명
    • DFS의 단계별 과정
    • DFS를 사용한 문제 해결 사례
  • DFS 구현
    • 스택 자료구조를 사용한 DFS 구현
    • 재귀를 사용한 DFS 구현
• 실습:
  • 파이썬을 사용한 DFS 구현 및 예제

# DFS 알고리즘 구현 (스택 사용)
def dfs_stack(graph, start):
    visited = set()
    stack = [start]
    result = []

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            stack.extend(set(graph[vertex]) - visited)

    return result

# DFS 알고리즘 구현 (재귀 사용)
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]

    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))

    return result

# 예제 실행
print("DFS 결과 (스택):", dfs_stack(graph, 0))  # [0, 2, 4, 3, 1]
print("DFS 결과 (재귀):", dfs_recursive(graph, 0))  # [0, 1, 3, 4, 2]

 

Day 6: 그래프 탐색 알고리즘의 비교 및 응용

• 강의 내용:
  • BFS와 DFS의 비교
    • BFS와 DFS의 장단점
    • 각 알고리즘의 사용 사례 및 적합성
  • 그래프 탐색 알고리즘의 응용
    • 최단 경로 찾기
    • 사이클 탐지
    • 연결 요소 찾기
• 실습:
  • 다양한 그래프 탐색 알고리즘의 응용 예제 구현

# 사이클 탐지 예제 (DFS 사용)
def detect_cycle(graph):
    def visit(vertex, visited, stack):
        visited.add(vertex)
        stack.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if visit(neighbor, visited, stack):
                    return True
            elif neighbor in stack:
                return True
        stack.remove(vertex)
        return False

    visited = set()
    stack = set()
    for vertex in graph:
        if vertex not in visited:
            if visit(vertex, visited, stack):
                return True
    return False

# 예제 실행
graph_with_cycle = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 4],
    3: [1, 4],
    4: [1, 2, 3]
}
print("사이클 탐지 결과:", detect_cycle(graph_with_cycle))  # True

 

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

• 강의 내용:
  • 그래프 탐색 알고리즘 종합 연습
    • 다양한 그래프 탐색 알고리즘 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • 프로젝트 준비
    • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 구현 계획 수립
• 실습:
  • 그래프 탐색 알고리즘 종합 연습 문제 풀기
  • 프로젝트 주제 및 계획 수립

### 종합 연습 문제 예시
1. 주어진 그래프에서 모든 연결 요소를 찾기
2. 주어진 그래프에서 특정 두 정점 간의 최단 경로 찾기 (BFS 사용)
3. 주어진 그래프에서 사이클 존재 여부 확인

### 프로젝트 주제 예시
1. 그래프 탐색을 활용한 소셜 네트워크 분석 도구
2. 그래프 탐색을 이용한 웹 크롤러 개발
3. 그래프 탐색을 사용한 네비게이션 시스템

### 프로젝트 요구사항 예시
1. 그래프 탐색을 활용한 소셜 네트워크 분석 도구:
   - 소셜 네트워크 데이터 입력 및 저장
   - 그래프 탐색 알고리즘을 통한 사용자 연결 분석
   - 분석 결과 출력 및 시각화

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 그래프 탐색 알고리즘 구현 (예: BFS, DFS 등)
3. 데이터 출력 및 시각화 모듈 구현

 

이 강의는 파이썬의 그래프 알고리즘, 특히 그래프의 개념과 용어, 그래프 탐색 알고리즘(BFS, DFS)의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!