Graph

Graph

• 우리가 흔히 생각하는 ‘그래프(chart)’가 아니라, 요소 간의 관계를 표현하는 자료구조임.
• 여러 요소가 어떻게 연결되어 있는지를 표현함.
• 예시: SNS에서 사용자는 서로 팔로우하거나 팔로우당함 → 단순 배열이나 트리로는 표현이 어려움.

그래프의 정의

그래프는 (V, E)로 구성됨:

• V: 노드 집합
• E: 노드 쌍의 집합 (간선)

방향 그래프 (Directed Graph)

간선에 방향이 있음: (u, v)는 u에서 v로의 연결을 의미함.

가중치 그래프 (Weighted Graph)

각 간선에 실수 값(weight)을 부여함: (V, E, W)

그래프 관련 용어

• Degree (차수): 한 노드에 연결된 간선 수
• 이분 그래프 (Bipartite): 노드를 두 그룹으로 나누고, 그룹 간에만 연결 존재
• 완전 그래프 (Complete Graph): 모든 노드 쌍이 연결됨
• 클리크 (Clique): 완전 부분 그래프

그래프 표현 방법

인접 행렬 (Adjacency Matrix)

정방형 행렬로 표현

• 장점: 접근 용이
• 단점: 공간 낭비 (특히 희소 그래프에서)

인접 리스트 (Adjacency List)

각 노드가 연결된 이웃 노드를 리스트로 저장

• 장점: 메모리 효율적
• 단점: 구조가 일정하지 않음

희소 vs 밀집 그래프

희소(Sparse) 그래프: 대부분의 노드가 적은 수의 연결만 가짐 (예: Twitter)

밀집(Dense) 그래프: 대부분의 노드가 서로 많이 연결되어 있음

그래프 연산

• 속성 질의 → 방향성 여부, 가중치 여부, 노드/간선 수
• 수정 → 노드/간선 추가, 가중치 변경 등
• 탐색 → 노드/간선/가중치 조회

그래프 순회 (Traversal)

트리와 다르게 루트가 없음 → 임의의 시작점에서 순회 시작

• DFS (깊이 우선 탐색): 가능한 깊게 들어감
• BFS (너비 우선 탐색): 가능한 넓게 퍼짐

DFS 예시

스택 또는 재귀 사용 → 무한 루프 방지를 위해 방문 체크 필요

BFS 예시

큐 사용 → 각 레벨의 노드를 모두 방문 후 다음으로 진행

연결 요소 (Connected Components)

노드들이 연결된 “덩어리”

• 서로 연결되지 않은 노드 집합은 서로 다른 컴포넌트임
• 그래프에서 독립된 섬처럼 존재함

스패닝 트리 (Spanning Tree)

그래프에서 모든 노드를 포함하면서 사이클이 없는 트리

• 여러 개의 스패닝 트리 가능

최소 신장 트리 (Minimum Spanning Tree, MST)

• 스패닝 트리 중 가중치의 합이 가장 작은 것 → 브루트 포스로 찾기는 매우 비효율적

MST 알고리즘

Prim’s Algorithm

임의의 노드에서 시작해 가장 가중치가 작은 간선을 계속 연결 → 최소 힙 또는 우선순위 큐 사용

• Top-down 방식

Prim’s Algorithm Output

• Output은 최소 신장 트리 (Minimum Spanning Tree, MST)입니다. 즉, 그래프 내 모든 노드를 연결하면서 전체 가중치 합이 최소인 트리 구조가 결과로 나옵니다.

사용할 자료구조 (DS)

• 후보 간선을 저장하는 리스트 C: → 최소 힙 (Min Heap / Priority Queue) 사용 → 각 간선 <v, u, w>를 넣되, 가중치 w가 가장 작은 것부터 꺼낼 수 있도록 함.

• 방문 여부 체크를 위한 집합 visited: → 중복 방문 방지 및 사이클 방지를 위해 필요

• 간선 정보를 저장할 그래프 구조: → 인접 리스트 (Adjacency List) 또는 인접 행렬 사용 가능

시간 복잡도 (Time Complexity) 일반적인 구현 → 우선순위 큐 사용

• 노드 수: 𝑉
• 간선 수: 𝐸
• 시간 복잡도: 𝑂(𝐸 log 𝑉)
• 이유: 최대 𝐸개의 간선을 우선순위 큐에 넣고 꺼내는 연산이 있으므로 log 𝑉 만큼의 비용이 듬.

Kruskal’s Algorithm

가중치가 가장 작은 간선부터 선택하면서 사이클을 만들지 않도록 트리를 점점 확장해 나감
→ 시작 노드 없이 간선 위주로 트리를 구성

• Bottom-up 방식

Kruskal’s Algorithm Output

• 입력: 가중치가 있는 무방향 그래프 G = {V, E, W}
• Output은 최소 신장 트리 (Minimum Spanning Tree, MST)입니다. 즉, 그래프 내 모든 노드를 연결하면서 전체 가중치 합이 최소인 트리 구조가 결과로 나옵니다.

사용할 자료구조 (DS)

• 가중치 기준 정렬된 간선 리스트 → 입력된 모든 간선을 <v, u, w> 형태로 오름차순 정렬하여 저장 아마 우선순위 큐(Heap)같은거 써야하지 않을까 싶음.

• 트리 병합을 위한 트리 ID 추적 구조 (예: 딕셔너리): → 각 노드가 어떤 트리에 속해 있는지를 저장 (예: tree_id[node] = id) → 두 노드가 서로 다른 트리에 속한 경우 병합 처리 (모든 관련 노드의 ID 갱신 필요)

• 간선 정보를 저장할 그래프 구조: → 인접 리스트 또는 간선 집합 (T) 형태로 저장 가능

시간 복잡도 (Time Complexity) Union-Find 없이 구현한 경우 기준

• 노드 수: 𝑉
• 간선 수: 𝐸
• 시간 복잡도:
  • 간선 정렬: O(𝐸 log 𝐸)
  • 트리 병합 (최악의 경우): O(𝐸 × 𝑉)
• 총 시간 복잡도: O(𝐸 log 𝐸 + 𝐸 × 𝑉)
• 이유: 정렬은 한 번만 수행되지만, 트리 병합 시 각 노드의 트리 ID를 모두 갱신해야 할 수 있기 때문