그래프란? — 노드, 엣지, 방향/무방향, 가중치

자료구조의 최종 보스, 그래프를 만나봅시다

배열, 링크드 리스트, 트리… 지금까지 배운 자료구조를 떠올려보세요

이것들은 모두 그래프의 특수한 형태입니다. 링크드 리스트는 일렬 그래프, 트리는 사이클 없는 그래프

그래프가 실제로 어디에 쓰이는지 살펴봅시다

인스타그램 팔로우는 방향 그래프입니다. 내가 팔로우해도 상대가 팔로우하지 않을 수 있으니까요

페이스북 친구는 무방향 그래프입니다. 친구를 맺으면 양쪽 다 친구가 됩니다

그래프의 종류를 코드로 확인합니다

# 무방향 그래프 — 양쪽 모두 추가
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# 방향 그래프 — 한쪽만 추가
digraph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []            # D에서 나가는 엣지 없음
}

# 가중치 그래프 — (목적지, 비용) 튜플
weighted = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 3)],
    'C': [('D', 1)],
    'D': []
}

면접에서 자주 나오는 그래프 용어를 정리합니다

트리는 사이클이 없는 연결 그래프입니다. DAG는 사이클이 없는 방향 그래프입니다

인스타그램 팔로우 관계를 어떤 그래프로 모델링해야 할까요?

DAG(Directed Acyclic Graph)에는 사이클이 존재할 수 있다

그래프의 세계 입장!