그래프 이론 기초: 노드와 간선

노드 (Node, Vertex): 점
간선 (Edge): 점들을 잇는 선

방향 그래프 (Directed):    A → B (한 방향)
무방향 그래프 (Undirected): A — B (양방향)
가중치 그래프 (Weighted):   A —[5]— B

# 5×5 행렬 — 노드 0~4
# matrix[i][j] = 1 이면 i→j 간선 존재

import numpy as np

# 무방향 그래프
matrix = np.array([
    # 0  1  2  3  4
    [0, 1, 1, 0, 0],  # 0 → 1, 2
    [1, 0, 0, 1, 0],  # 1 → 0, 3
    [1, 0, 0, 1, 1],  # 2 → 0, 3, 4
    [0, 1, 1, 0, 1],  # 3 → 1, 2, 4
    [0, 0, 1, 1, 0],  # 4 → 2, 3
])

# 무방향 그래프는 대칭 — matrix[i][j] == matrix[j][i]


# 0번 노드의 이웃 찾기 — O(V) (V=노드 수)
def neighbors_matrix(matrix, node):
    return [i for i, connected in enumerate(matrix[node]) if connected]


print(neighbors_matrix(matrix, 0))  # [1, 2]


# 공간: O(V²) — 노드 1만 개면 1억 원소
# 장점: 두 노드의 연결 여부 O(1) 확인
# 단점: 희소 그래프(간선 적음)에 메모리 낭비

# 각 노드별 연결된 노드 목록만 저장

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2, 4],
    4: [2, 3],
}

# 0번 노드의 이웃 — O(1)
print(graph[0])  # [1, 2]


# 공간: O(V + E) — 간선 수만큼
# 장점: 희소 그래프에 효율적
# 단점: 두 노드 연결 여부 확인이 O(degree)


# 가중치 그래프
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)],
}

# A의 이웃과 거리
for neighbor, weight in weighted_graph['A']:
    print(f"A → {neighbor}: {weight}")
# A → B: 4
# A → C: 2

# 사용자 간 팔로우 관계 (방향 그래프)
follows = {
    'alice':   {'bob', 'charlie'},
    'bob':     {'alice'},                # 양방향
    'charlie': {'dave', 'eve'},
    'dave':    {'alice'},
    'eve':     {'alice', 'bob'},
}

# alice의 팔로워 (alice를 팔로우하는 사람)
def get_followers(graph, user):
    return {u for u, follows_set in graph.items() if user in follows_set}


print(get_followers(follows, 'alice'))  # {'bob', 'dave', 'eve'}

# alice가 팔로우하는 사람
print(follows['alice'])  # {'bob', 'charlie'}

# 상호 팔로우 (mutuals)
mutuals = follows['alice'] & get_followers(follows, 'alice')
print(mutuals)  # {'bob'}

# Node.js 패키지 의존성 그래프
deps = {
    'my-app': {'react', 'next'},
    'react':  {'react-dom'},
    'react-dom': set(),
    'next':   {'react', 'react-dom'},
}


# 모든 (직간접) 의존성 — DFS
def all_dependencies(graph, package, visited=None):
    if visited is None:
        visited = set()
    if package in visited:
        return visited
    visited.add(package)
    for dep in graph.get(package, []):
        all_dependencies(graph, dep, visited)
    return visited


print(all_dependencies(deps, 'my-app'))
# {'my-app', 'react', 'next', 'react-dom'}

# React 컴포넌트는 트리 구조 (특수한 그래프)
component_tree = {
    'App': ['Header', 'Main', 'Footer'],
    'Header': ['Logo', 'Nav'],
    'Nav': ['NavItem1', 'NavItem2', 'NavItem3'],
    'Main': ['Article', 'Sidebar'],
    'Article': ['Title', 'Content'],
    'Sidebar': ['AdBox'],
    'Footer': [],
    'Logo': [], 'NavItem1': [], 'NavItem2': [], 'NavItem3': [],
    'Title': [], 'Content': [], 'AdBox': [],
}


def print_tree(graph, node, depth=0):
    print('  ' * depth + node)
    for child in graph.get(node, []):
        print_tree(graph, child, depth + 1)


print_tree(component_tree, 'App')
# App
#   Header
#     Logo
#     Nav
#       NavItem1
#       ...
#   Main
#     ...