[알고리즘] Week 6: 고급 그래프 알고리즘 - 강한 연결 요소와 위상 정렬

Day 1: 강한 연결 요소 (Strongly Connected Components, SCC)

• 강의 내용:
  • 강한 연결 요소의 개념
    • 강한 연결 요소란 무엇인가?
    • 그래프의 SCC를 찾는 중요성 및 응용 사례
  • 강한 연결 요소 탐색 알고리즘
    • 코사라주 알고리즘 (Kosaraju's Algorithm)
    • 타잔 알고리즘 (Tarjan's Algorithm)
• 실습:
  • 간단한 예제 그래프에서 SCC 찾기

# 코사라주 알고리즘을 사용한 SCC 찾기
from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

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

    def dfs(self, v, visited, stack):
        visited[v] = True
        for neighbour in self.graph[v]:
            if not visited[neighbour]:
                self.dfs(neighbour, visited, stack)
        stack.append(v)

    def transpose(self):
        g_t = Graph(self.V)
        for i in self.graph:
            for j in self.graph[i]:
                g_t.add_edge(j, i)
        return g_t

    def fill_order(self, v, visited, stack):
        visited[v] = True
        for neighbour in self.graph[v]:
            if not visited[neighbour]:
                self.fill_order(neighbour, visited, stack)
        stack.append(v)

    def scc_kosaraju(self):
        stack = []
        visited = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                self.fill_order(i, visited, stack)

        gr = self.transpose()
        visited = [False] * self.V

        scc = []
        while stack:
            i = stack.pop()
            if not visited[i]:
                stack_component = []
                gr.dfs(i, visited, stack_component)
                scc.append(stack_component)
        return scc

# 예제 실행
g = Graph(5)
g.add_edge(1, 0)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(0, 3)
g.add_edge(3, 4)

print("코사라주 알고리즘에 의한 SCC:")
print(g.scc_kosaraju())  # [[0, 1, 2], [3], [4]]

 

Day 2: 타잔 알고리즘 (Tarjan's Algorithm)

• 강의 내용:
  • 타잔 알고리즘의 개념
    • 타잔 알고리즘이란 무엇인가?
    • 타잔 알고리즘의 동작 원리
  • 타잔 알고리즘의 시간 복잡도
    • 시간 복잡도: O(V + E)
• 실습:
  • 파이썬을 사용한 타잔 알고리즘 구현 및 예제

# 타잔 알고리즘을 사용한 SCC 찾기
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices
        self.time = 0

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

    def scc_util(self, u, low, disc, stack_member, stack, scc):
        disc[u] = self.time
        low[u] = self.time
        self.time += 1
        stack_member[u] = True
        stack.append(u)

        for v in self.graph[u]:
            if disc[v] == -1:
                self.scc_util(v, low, disc, stack_member, stack, scc)
                low[u] = min(low[u], low[v])
            elif stack_member[v]:
                low[u] = min(low[u], disc[v])

        if low[u] == disc[u]:
            component = []
            while stack[-1] != u:
                w = stack.pop()
                component.append(w)
                stack_member[w] = False
            w = stack.pop()
            component.append(w)
            stack_member[w] = False
            scc.append(component)

    def scc_tarjan(self):
        disc = [-1] * self.V
        low = [-1] * self.V
        stack_member = [False] * self.V
        stack = []
        scc = []

        for i in range(self.V):
            if disc[i] == -1:
                self.scc_util(i, low, disc, stack_member, stack, scc)
        return scc

# 예제 실행
g = Graph(5)
g.add_edge(1, 0)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(0, 3)
g.add_edge(3, 4)

print("타잔 알고리즘에 의한 SCC:")
print(g.scc_tarjan())  # [[1, 2, 0], [4], [3]]

 

Day 3: 위상 정렬 (Topological Sorting)

• 강의 내용:
  • 위상 정렬의 개념
    • 위상 정렬이란 무엇인가?
    • 위상 정렬의 동작 원리
  • 위상 정렬의 중요성
    • 작업 스케줄링 및 의존성 해결
    • 사이클이 없는 유향 그래프 (DAG)에서의 응용
• 실습:
  • 파이썬을 사용한 위상 정렬 구현 및 예제

# 위상 정렬 구현
def topological_sort_util(v, visited, stack, graph):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            topological_sort_util(i, visited, stack, graph)
    stack.insert(0, v)

def topological_sort(graph, vertices):
    visited = [False] * vertices
    stack = []

    for i in range(vertices):
        if not visited[i]:
            topological_sort_util(i, visited, stack, graph)
    return stack

# 예제 실행
graph = defaultdict(list)
graph[5].append(2)
graph[5].append(0)
graph[4].append(0)
graph[4].append(1)
graph[2].append(3)
graph[3].append(1)
vertices = 6

print("위상 정렬 결과:")
print(topological_sort(graph, vertices))  # [5, 4, 2, 3, 1, 0]

 

Day 4: 칸 알고리즘 (Kahn's Algorithm)

• 강의 내용:
  • 칸 알고리즘의 개념
    • 칸 알고리즘이란 무엇인가?
    • 칸 알고리즘의 동작 원리
  • 칸 알고리즘의 시간 복잡도
    • 시간 복잡도: O(V + E)
• 실습:
  • 파이썬을 사용한 칸 알고리즘 구현 및 예제

# 칸 알고리즘을 사용한 위상 정렬
def kahn_topological_sort(graph, vertices):
    in_degree = [0] * vertices
    for i in graph:
        for j in graph[i]:
            in_degree[j] += 1

    queue = deque([i for i in range(vertices) if in_degree[i] == 0])
    top_order = []

    while queue:
        u = queue.popleft()
        top_order.append(u)

        for i in graph[u]:
            in_degree[i] -= 1
            if in_degree[i] == 0:
                queue.append(i)

    if len(top_order) == vertices:
        return top_order
    else:
        return "그래프에 사이클이 있습니다."

# 예제 실행
graph = defaultdict(list)
graph[5].append(2)
graph[5].append(0)
graph[4].append(0)
graph[4].append(1)
graph[2].append(3)
graph[3].append(1)
vertices = 6

print("칸 알고리즘에 의한 위상 정렬 결과:")
print(kahn_topological_sort(graph, vertices))  # [4, 5, 0, 2, 3, 1]

 

Day 5: 고급 그래프 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 강한 연결 요소 및 위상 정렬 문제 해결
  • 고급 그래프 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 그래프에서 코사라주 알고리즘을 사용하여 강한 연결 요소를 찾으세요.
2. 주어진 그래프에서 타잔 알고리즘을 사용하여 강한 연결 요소를 찾으세요.
3. 주어진 그래프에서 위상 정렬을 수행하세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 그래프 데이터 처리 도구 개발
2. 실시간 작업 스케줄링 시스템

### 프로젝트 요구사항 예시
1. 대규모 그래프 데이터 처리 도구:
   - 대규모 그래프 데이터셋 입력 및 저장
   - 고급 그래프 알고리즘을 통한 데이터 처리
   - 처리된 데이터 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 고급 그래프 알고리즘 구현 (SCC, 위상 정렬 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

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