그래프 이론 - 지하철 노선도부터 알고리즘까지

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],         # A는 B, C와 연결됨
    'B': ['A', 'D', 'E'],    # B는 A, D, E와 연결됨
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 방향 그래프
directed_graph = {
    'A': ['B', 'C'],      # A에서 B, C로 갈 수 있음
    'B': ['D'],           # B에서 D로만 갈 수 있음
    'C': [],              # C에서는 나가는 엣지 없음
    'D': ['A']            # D에서 A로 갈 수 있음 (사이클)
}

# 가중치 그래프
weighted_graph = {
    'A': [('B', 4), ('C', 2)],     # A→B 비용 4, A→C 비용 2
    'B': [('D', 3), ('E', 1)],
    'C': [('F', 5)],
    'D': [],
    'E': [('F', 2)],
    'F': []
}

line_2 = {
    '강남': ['역삼', '교대'],
    '역삼': ['강남', '선릉'],
    '선릉': ['역삼', '삼성'],
    '삼성': ['선릉', '종합운동장'],
    # ... 계속
}

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited

# 실행
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')  # 출력: A B D E F C

from collections import deque

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

# 실행
bfs(graph, 'A')  # 출력: A B C D E F

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (거리, 노드)
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# 실행
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 3), ('E', 1)],
    'C': [('F', 5)],
    'D': [],
    'E': [('F', 2)],
    'F': []
}

result = dijkstra(weighted_graph, 'A')
print(result)  # A에서 각 노드까지 최단 거리

social_network = {
    '철수': ['영희', '민수', '지영'],
    '영희': ['철수', '민수'],
    '민수': ['철수', '영희', '지영', '동수'],
    '지영': ['철수', '민수'],
    '동수': ['민수']
}

def recommend_friends(network, user):
    friends = set(network[user])
    friends_of_friends = set()
    
    for friend in friends:
        for fof in network[friend]:
            if fof != user and fof not in friends:
                friends_of_friends.add(fof)
    
    return friends_of_friends

print(recommend_friends(social_network, '철수'))
# 출력: {'동수'}

def has_cycle_dfs(graph):
    visited = set()
    rec_stack = set()  # 현재 재귀 스택
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True  # 사이클 발견!
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    
    return False

# 테스트
cycle_graph = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']  # A → B → C → A (사이클)
}

print(has_cycle_dfs(cycle_graph))  # True

from collections import deque, defaultdict

def topological_sort(graph):
    in_degree = defaultdict(int)
    
    # 진입 차수 계산
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 진입 차수가 0인 노드부터 시작
    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result

# 수강 과목 의존성
courses = {
    '프로그래밍기초': ['자료구조'],
    '이산수학': ['알고리즘'],
    '자료구조': ['알고리즘'],
    '알고리즘': []
}

print(topological_sort(courses))
# 출력: ['프로그래밍기초', '이산수학', '자료구조', '알고리즘']

# 간단한 웹 크롤러 구조
def crawl(start_url):
    visited = set()
    queue = deque([start_url])
    
    while queue:
        url = queue.popleft()
        if url in visited:
            continue
        
        visited.add(url)
        links = get_links(url)  # 페이지에서 링크 추출
        queue.extend(links)