그래프 표현 — 인접 리스트 vs 인접 행렬

from collections import defaultdict

# 인접 리스트 구축 — 무방향 그래프
def build_graph(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)    # 무방향이므로 양쪽 추가
    return graph

edges = [('A','B'), ('A','C'), ('B','D'), ('C','D')]
g = build_graph(edges)
print(dict(g))
# {'A': ['B','C'], 'B': ['A','D'], 'C': ['A','D'], 'D': ['B','C']}

# 인접 행렬 구축
def build_matrix(n, edges):
    matrix = [[0] * n for _ in range(n)]
    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1    # 무방향
    return matrix

# 노드 0,1,2,3 / 엣지 (0,1),(0,2),(1,3),(2,3)
m = build_matrix(4, [(0,1),(0,2),(1,3),(2,3)])
for row in m:
    print(row)
# [0, 1, 1, 0]
# [1, 0, 0, 1]
# [1, 0, 0, 1]
# [0, 1, 1, 0]