[자료구조] Week 8: 그래프 I - 그래프의 개념과 표현 방법

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

• 강의 내용:
  • 그래프의 정의와 특징
    • 그래프의 개념 (정점과 간선으로 이루어진 자료구조)
    • 방향 그래프와 무방향 그래프
  • 그래프의 기본 용어
    • 정점 (Vertex), 간선 (Edge), 인접 (Adjacent), 경로 (Path), 사이클 (Cycle), 연결성 (Connectivity)
  • 그래프와 트리의 차이
• 실습:
  • 그래프의 기본 용어와 개념을 시각적으로 설명

# 그래프의 기본 용어 설명
# - 정점(Vertex): 그래프의 노드
# - 간선(Edge): 정점 간의 연결
# - 인접(Adjacent): 간선으로 연결된 두 정점
# - 경로(Path): 정점과 간선의 연속
# - 사이클(Cycle): 시작 정점과 끝 정점이 동일한 경로
# - 연결성(Connectivity): 모든 정점이 연결된 상태

# 그래프의 예시를 시각적으로 설명
# 예:
#     A
#    / \
#   B - C
#    \ /
#     D

 

Day 2: 그래프의 표현 방법

• 강의 내용:
  • 그래프의 표현 방법
    • 인접 행렬 (Adjacency Matrix)
    • 인접 리스트 (Adjacency List)
  • 각 표현 방법의 장단점
• 실습:
  • 인접 행렬을 사용한 그래프 표현

# 인접 행렬을 사용한 그래프 표현
import numpy as np

class GraphAdjMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = np.zeros((num_vertices, num_vertices))

    def add_edge(self, u, v):
        self.adj_matrix[u][v] = 1
        self.adj_matrix[v][u] = 1  # 무방향 그래프의 경우

    def display(self):
        print(self.adj_matrix)

# 그래프 사용 예제
graph = GraphAdjMatrix(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.display()
# Output:
# [[0. 1. 1. 0.]
#  [1. 0. 1. 1.]
#  [1. 1. 0. 0.]
#  [0. 1. 0. 0.]]

 

Day 3: 인접 리스트를 사용한 그래프 표현

• 강의 내용:
  • 인접 리스트의 정의와 특징
    • 인접 리스트의 개념
    • 인접 리스트의 장단점
• 실습:
  • 인접 리스트를 사용한 그래프 표현

# 인접 리스트를 사용한 그래프 표현
class GraphAdjList:
    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)
        self.adj_list[v].append(u)  # 무방향 그래프의 경우

    def display(self):
        for i in range(self.num_vertices):
            print(f"{i}: {self.adj_list[i]}")

# 그래프 사용 예제
graph = GraphAdjList(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.display()
# Output:
# 0: [1, 2]
# 1: [0, 2, 3]
# 2: [0, 1]
# 3: [1]

 

Day 4: 방향 그래프와 가중 그래프

• 강의 내용:
  • 방향 그래프 (Directed Graph)
    • 방향 그래프의 개념과 특징
  • 가중 그래프 (Weighted Graph)
    • 가중 그래프의 개념과 특징
  • 그래프 표현 방법의 확장
    • 방향 그래프와 가중 그래프의 인접 행렬 및 인접 리스트 표현
• 실습:
  • 방향 그래프와 가중 그래프의 인접 리스트 구현

# 방향 그래프와 가중 그래프의 인접 리스트 표현
class WeightedGraphAdjList:
    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))
        # 방향 그래프이므로 반대 방향은 추가하지 않음

    def display(self):
        for i in range(self.num_vertices):
            print(f"{i}: {self.adj_list[i]}")

# 가중 그래프 사용 예제
graph = WeightedGraphAdjList(4)
graph.add_edge(0, 1, 2)
graph.add_edge(0, 2, 4)
graph.add_edge(1, 2, 1)
graph.add_edge(1, 3, 7)
graph.display()
# Output:
# 0: [(1, 2), (2, 4)]
# 1: [(2, 1), (3, 7)]
# 2: []
# 3: []

 

Day 5: 그래프의 탐색 (DFS, BFS)

• 강의 내용:
  • 깊이 우선 탐색 (Depth-First Search, DFS)
    • DFS의 개념과 알고리즘
    • 재귀적 구현과 비재귀적 구현 (스택 사용)
  • 너비 우선 탐색 (Breadth-First Search, BFS)
    • BFS의 개념과 알고리즘
    • 큐를 사용한 구현
• 실습:
  • DFS와 BFS의 구현

# 깊이 우선 탐색 (DFS) 구현
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next in graph.adj_list[start]:
        if next not in visited:
            dfs(graph, next, visited)

# 너비 우선 탐색 (BFS) 구현
def bfs(graph, start):
    visited = set()
    queue = [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            queue.extend([v for v in graph.adj_list[vertex] if v not in visited])

# 그래프 탐색 예제
graph = GraphAdjList(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
print("DFS 탐색 결과:")
dfs(graph, 0)  # 0 1 2 3

print("\nBFS 탐색 결과:")
bfs(graph, 0)  # 0 1 2 3

 

Day 6: 그래프의 응용

• 강의 내용:
  • 그래프의 실제 응용 사례
    • 소셜 네트워크 분석
    • 최단 경로 탐색
    • 웹 크롤링
  • 그래프를 사용한 문제 해결
    • 그래프 색칠 문제
    • 위상 정렬
• 실습:
  • 그래프를 사용한 응용 예제

# 위상 정렬 알고리즘 (Kahn's Algorithm)
from collections import deque

def topological_sort(graph):
    in_degree = {i: 0 for i in range(graph.num_vertices)}
    for i in range(graph.num_vertices):
        for j in graph.adj_list[i]:
            in_degree[j] += 1
    queue = deque([i for i in in_degree if in_degree[i] == 0])
    topo_order = []
    while queue:
        vertex = queue.popleft()
        topo_order.append(vertex)
        for neighbor in graph.adj_list[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    if len(topo_order) == graph.num_vertices:
        return topo_order
    else:
        return "Graph has a cycle"

# 위상 정렬 예제
graph = GraphAdjList(6)
graph.add_edge(5, 2)
graph.add_edge(5, 0)
graph.add_edge(4, 0)
graph.add_edge(4, 1)
graph.add_edge(2, 3)
graph.add_edge(3, 1)
print("위상 정렬 결과:")
print(topological_sort(graph))  # [5, 4, 2, 3, 1, 0]

 

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

• 강의 내용:
  • 그래프를 사용한 종합 연습 문제 풀이
    • 다양한 그래프 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 그래프를 활용한 간단한 프로그램 구현
    • 예: 소셜 네트워크 분석
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 그래프에서 사이클 존재 여부 확인
def has_cycle(graph):
    visited = set()
    def dfs(v, parent):
        visited.add(v)
        for neighbor in graph.adj_list[v]:
            if neighbor not in visited:
                if dfs(neighbor, v):
                    return True
            elif parent != neighbor:
                return True
        return False
    for vertex in range(graph.num_vertices):
        if vertex not in visited:
            if dfs(vertex, -1):
                return True
    return False

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

# 미니 프로젝트 예제: 소셜 네트워크 분석
class SocialNetwork:
    def __init__(self, num_people):
        self.graph = GraphAdjList(num_people)

    def add_friendship(self, person1, person2):
        self.graph.add_edge(person1, person2)

    def suggest_friends(self, person):
        friends = set(self.graph.adj_list[person])
        suggestions = set()
        for friend in friends:
            for friend_of_friend in self.graph.adj_list[friend]:
                if friend_of_friend != person and friend_of_friend not in friends:
                    suggestions.add(friend_of_friend)
        return suggestions

# 소셜 네트워크 분석 예제
network = SocialNetwork(5)
network.add_friendship(0, 1)
network.add_friendship(0, 2)
network.add_friendship(1, 2)
network.add_friendship(1, 3)
network.add_friendship(2, 3)
network.add_friendship(3, 4)
print("사용자 0에게 친구 추천:", network.suggest_friends(0))  # {3}
print("사용자 1에게 친구 추천:", network.suggest_friends(1))  # {4}

 

이 강의는 파이썬의 자료구조 중 그래프의 기본 개념과 표현 방법을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!