그래프 (Graph) 자료구조

📌 개요

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다.
그래프는 정점 간의 연결 관계를 표현하는 데 사용되며, 다양한 실생활 문제(지도 네비게이션, SNS 관계망, 네트워크 등)에서 활용됩니다.

✅ 그래프의 특징

• 정점(Vertex, Node)과 간선(Edge)으로 구성
• 방향성(Directed, Undirected), 가중치(Weighted, Unweighted) 여부에 따라 종류가 나뉨
• DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 탐색 방법이 존재
• 최단 경로 탐색, 최소 신장 트리(MST) 등의 알고리즘에서 활용됨

---

📌 그래프의 용어

용어	설명
정점(Vertex, 노드)	그래프의 구성 요소
간선(Edge)	정점 간의 연결
인접(Adjacent)	두 정점이 직접 연결된 상태
차수(Degree)	특정 정점과 연결된 간선 개수
가중치(Weight)	간선에 부여된 값 (가중 그래프)
경로(Path)	한 정점에서 다른 정점으로 가는 방법
사이클(Cycle)	출발점과 도착점이 같은 경로

---

📌 그래프의 종류

1. 방향 그래프 (Directed Graph)

• 간선에 방향이 있는 그래프
• A → B 이면 B → A는 성립하지 않음
• 예제: 웹 페이지 링크, 도로망(일방통행)

2. 무방향 그래프 (Undirected Graph)

• 간선에 방향이 없는 그래프
• A - B 이면 B - A도 성립함
• 예제: 친구 관계(SNS), 지하철 노선도

3. 가중 그래프 (Weighted Graph)

• 간선에 가중치(Weight)가 존재하는 그래프
• 예제: 도로 거리, 네트워크 대역폭

4. 트리 (Tree)

• 사이클이 없는 특수한 형태의 그래프
• N개의 정점과 N-1개의 간선을 가짐
• 최소 신장 트리(MST), 이진 탐색 트리(BST) 등에서 활용

---

📌 그래프의 표현 방법

그래프는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) 두 가지 방식으로 표현할 수 있습니다.

1. 인접 행렬 (Adjacency Matrix)

• 2차원 배열을 사용하여 정점 간 연결 관계를 저장
• 메모리 사용량: O(N²)
• 모든 정점 간의 관계를 빠르게 확인 가능 (O(1))

# 5개의 정점이 있는 그래프
INF = float('inf')  # 연결되지 않은 경우 무한대

graph = [
    [0, 2, INF, 1, INF],
    [2, 0, 3, 2, INF],
    [INF, 3, 0, INF, 1],
    [1, 2, INF, 0, 4],
    [INF, INF, 1, 4, 0]
]

print(graph)  # 2차원 배열 출력

✅ 장점: 빠른 조회 (O(1))
❌ 단점: 공간 낭비 (연결이 적은 경우 비효율적)

---

2. 인접 리스트 (Adjacency List)

• 각 정점마다 연결된 정점을 리스트로 저장
• 메모리 사용량: O(V + E)
• 탐색 속도는 행렬보다 느리지만 메모리 효율적

graph = {
    0: [(1, 2), (3, 1)],  # 정점 0과 연결된 노드 (노드, 가중치)
    1: [(0, 2), (2, 3), (3, 2)],
    2: [(1, 3), (4, 1)],
    3: [(0, 1), (1, 2), (4, 4)],
    4: [(2, 1), (3, 4)]
}

print(graph)  # 딕셔너리로 표현된 인접 리스트 출력

✅ 장점: 메모리 절약 (간선이 적은 경우 효율적)
❌ 단점: 특정 정점 간 연결 여부 확인이 느림 (O(V))

---

📌 그래프 탐색 알고리즘

그래프에서 특정 정점을 방문하거나 경로를 찾기 위해 DFS(깊이 우선 탐색) 및 BFS(너비 우선 탐색) 를 사용합니다.

1. 깊이 우선 탐색 (DFS)

✅ 특징:

• 스택(Stack) 또는 재귀(Recursion) 사용
• 모든 경로를 탐색해야 할 때 유용
• 시간 복잡도: O(V + E)

def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=" ")

    for neighbor, _ in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

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

visited = set()
dfs(graph, 0, visited)  # 출력: 0 1 2 4 3

✅ 사용 예시: 미로 탐색, 백트래킹(Backtracking)

---

2. 너비 우선 탐색 (BFS)

✅ 특징:

• 큐(Queue) 사용
• 최단 경로 찾기에 유용
• 시간 복잡도: O(V + E)

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set([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, 0)  # 출력: 0 1 3 2 4

✅ 사용 예시: 최단 거리 탐색 (네비게이션, 최단 경로 문제)

---

📌 그래프 알고리즘

1. 최단 경로 알고리즘

• 다익스트라(Dijkstra) → 단일 출발점에서 최단 거리 (O(V log V))
• 플로이드-워셜(Floyd-Warshall) → 모든 쌍 최단 거리 (O(V³))
• 벨만-포드(Bellman-Ford) → 음수 가중치 허용 (O(VE))

2. 최소 신장 트리 (MST)

• 크루스칼(Kruskal) → 유니온 파인드(Union-Find) 사용
• 프림(Prim) → 우선순위 큐 사용

---

📌 그래프 자료구조의 장단점

✅ 장점

• 복잡한 관계 표현 가능 (네트워크, 지도, 소셜미디어 등)
• DFS, BFS 등을 이용해 다양한 문제 해결 가능
• 다익스트라, 크루스칼 등 다양한 최적화 알고리즘과 결합 가능

❌ 단점

• 메모리 사용량이 많음 (인접 행렬 방식)
• 특정 정점 탐색 시 시간이 오래 걸릴 수 있음 (인접 리스트 방식)
• 순환(Cycle) 처리 및 중복 탐색을 방지해야 함

---

📌 결론

• 그래프는 정점과 간선을 활용하여 관계를 표현하는 강력한 자료구조
• DFS, BFS 탐색 기법을 활용하면 그래프의 다양한 문제를 해결 가능
• 최단 경로, 최소 신장 트리, 네트워크 분석 등 다양한 분야에서 활용됨

🚀 그래프는 자료구조와 알고리즘의 핵심 개념이므로, 반드시 익혀야 합니다!