그래프(Graph): 네트워크와 관계 데이터를 표현하는 강력한 자료구조

🔹 그래프란?

1. 그래프(Graph)의 정의

그래프(Graph)는 노드(Node, 정점)와 엣지(Edge, 간선)로 구성된 비선형 데이터 구조로, 객체 간의 관계를 표현하는 데 사용됩니다. 그래프는 소셜 네트워크, 지도 경로 탐색, 웹 크롤링, 네트워크 라우팅 등 다양한 분야에서 필수적인 자료구조입니다.

✅ 그래프의 주요 특징:

• 정점(Vertex, Node): 데이터를 저장하는 요소
• 간선(Edge): 노드 간의 관계를 나타내는 연결선
• 방향 그래프(Directed Graph, 유향 그래프)와 무방향 그래프(Undirected Graph, 무향 그래프)로 구분
• 가중 그래프(Weighted Graph)와 비가중 그래프(Unweighted Graph)로 구분

📌 그래프는 네트워크 구조를 모델링하는 데 최적화된 자료구조입니다.

---

🔹 그래프의 유형

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

✅ 노드 간의 간선이 방향성을 가지지 않는 그래프

✔️ 예제:

    A ---- B
    |      |
    C ---- D

📌 소셜 네트워크에서 친구 관계를 나타내는 데 활용됩니다.

2. 방향 그래프(Directed Graph, 유향 그래프)

✅ 간선이 방향성을 가지며, 한쪽으로만 이동 가능한 그래프

✔️ 예제:

    A → B → C
    ↑    ↓
    D ← E

📌 웹페이지 링크, 네트워크 패킷 흐름 등을 모델링하는 데 사용됩니다.

3. 가중 그래프(Weighted Graph)

✅ 각 간선이 특정 가중치(비용)를 가지는 그래프

✔️ 예제:

    A --(4)-- B
    |        |
  (2)      (3)
    |        |
    C --(1)-- D

📌 GPS 내비게이션에서 최단 경로를 계산하는 데 사용됩니다.

4. 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)

✅ 그래프를 표현하는 방법으로, 효율성에 따라 선택됨

✔️ 인접 행렬:

  A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0

📌 O(1)으로 간선 확인 가능하지만, 메모리 사용량이 많음

✔️ 인접 리스트 (Python 표현):

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

📌 메모리 사용이 적고, 연결된 노드만 저장하여 효율적

---

🔹 그래프 탐색 알고리즘

1. 깊이 우선 탐색(DFS, Depth-First Search) - O(V+E)

✅ 한 경로를 끝까지 탐색한 후, 다시 돌아가 다른 경로를 탐색하는 방식

✔️ DFS 예제 (Python):

def dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node, end=' ')
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
visited = set()
dfs(graph, 'A', visited)  # 출력: A B D E F C

📌 DFS는 백트래킹, 미로 탐색, 순열 생성 등에 활용됩니다.

2. 너비 우선 탐색(BFS, Breadth-First Search) - O(V+E)

✅ 현재 노드의 모든 인접 노드를 먼저 방문한 후, 다음 깊이로 이동하는 방식

✔️ BFS 예제 (Python):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            queue.extend(graph[node])

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
bfs(graph, 'A')  # 출력: A B C D E F

📌 BFS는 최단 경로 탐색, 네트워크 탐색, 웹 크롤링 등에 활용됩니다.

---

🔹 최단 경로 알고리즘

1. 다익스트라 알고리즘(Dijkstra’s Algorithm) - O((V+E) log V)

✅ 가중 그래프에서 출발점에서 모든 노드까지의 최단 경로를 찾는 알고리즘

✔️ 다익스트라 알고리즘 예제 (Python):

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))

📌 네비게이션 시스템, 네트워크 경로 탐색에 사용됩니다.

---

📌 결론

✅ 그래프(Graph)는 네트워크, 지도, 관계 데이터를 표현하는 핵심 데이터 구조입니다.
✅ DFS, BFS, 다익스트라 알고리즘 등을 활용하여 그래프 탐색 및 최단 경로를 찾을 수 있습니다.
✅ 그래프는 소셜 네트워크 분석, 검색 엔진, 인공지능 등 다양한 분야에서 활용됩니다.