그래프 (Graph)

---

1. 그래프의 정의

---

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 정점 간의 관계를 나타내는 데 사용됩니다.
그래프는 네트워크, 소셜 관계, 경로 탐색, 작업 스케줄링 등 다양한 문제를 모델링하는 데 필수적인 구조입니다.

그래프의 주요 구성 요소

1. 정점(Vertex): 그래프를 구성하는 개체. 사람, 도시, 컴퓨터 등 다양한 개체를 나타낼 수 있습니다.
2. 간선(Edge): 두 정점을 연결하는 선. 관계, 경로, 연결을 의미합니다.
3. 인접(Adjacency): 두 정점이 간선으로 연결된 상태.
4. 차수(Degree):
   • 내차수(In-degree): 정점으로 들어오는 간선의 수.
   • 외차수(Out-degree): 정점에서 나가는 간선의 수.

---

2. 그래프의 종류

---

방향성에 따른 분류

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

   • 간선에 방향이 없으며, 연결된 두 정점은 대칭적 관계를 가짐.
   • 예: 친구 관계, 도로 네트워크.

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

   • 간선에 방향이 있어, 두 정점 간의 관계가 비대칭적.
   • 예: 트위터 팔로우 관계, 함수 호출 그래프.

---

가중치에 따른 분류

1. 가중치 그래프 (Weighted Graph)

   • 간선마다 가중치가 부여된 그래프.
   • 예: 도로 네트워크에서 거리나 비용, 시간.

2. 비가중치 그래프 (Unweighted Graph)

   • 간선에 가중치가 없는 그래프.

---

구조에 따른 분류

1. 순환 그래프 (Cyclic Graph)

   • 정점에서 출발해 다시 출발점으로 돌아오는 경로(사이클)가 존재하는 그래프.
   • 예: 네트워크 라우팅.

2. 비순환 그래프 (Acyclic Graph)

   • 사이클이 없는 그래프.
   • 예: 작업 스케줄링.

3. 완전 그래프 (Complete Graph)

   • 모든 정점이 서로 연결된 그래프.
   • 예: 소규모 네트워크.

4. 부분 그래프 (Subgraph)

   • 기존 그래프의 일부 정점과 간선으로 구성된 그래프.

5. 트리 (Tree)

   • 사이클이 없는 연결 그래프. 모든 정점이 하나의 경로로 연결됩니다.

---

3. 그래프의 표현 방식

---

1. 인접 행렬 (Adjacency Matrix)

• 2차원 배열을 사용하여 그래프의 간선 정보를 저장.
• 각 행과 열은 정점을 나타내며, 배열 값은 간선의 존재를 나타냅니다.

구현 예시

0  1  2
1 [0, 1, 1]
2 [1, 0, 1]

장단점

• 장점: 간선의 존재 여부를 빠르게 확인 가능($O(1)$).
• 단점: 희소 그래프에서 비효율적(공간 복잡도 $O(V^2)$).

2. 인접 리스트 (Adjacency List)

• 각 정점마다 연결된 정점의 리스트를 저장.
• 연결된 정점만 저장하므로 공간 효율적.

구현 예시

0 -> [1, 2]
1 -> [0, 2]

장단점

• 장점: 공간 효율적($O(V + E)$).
• 단점: 특정 간선의 존재 여부를 확인하는 데 시간이 오래 걸림($O(V)$).

4. 그래프 순회 알고리즘

---

그래프를 탐색하는 알고리즘은 모든 정점 또는 특정 경로를 탐색하는 데 사용됩니다.

1. 너비 우선 탐색 (BFS)

• 큐(Queue)를 사용하여 정점을 레벨 순으로 탐색.
• 근접한 정점을 먼저 방문하며, 최단 경로 탐색에 유용.
• 시간 복잡도: $O(V + E)$.

c언어 구현

void BFS(int start) {
    Queue q;
    enqueue(&q, start);
    visited[start] = 1;
    while (!isEmpty(&q)) {
        int current = dequeue(&q);
        printf("%d ", current);
        for (int i = 0; i < numVertices; i++) {
            if (graph[current][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }
}

2. 깊이 우선 탐색 (DFS)

• 스택(Stack) 또는 재귀(Recursion)를 사용하여 정점을 깊게 탐색.
• 시간 복잡도: $O(V + E)$.

c언어 구현

void DFS(int vertex) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    for (int i = 0; i < numVertices; i++) {
        if (graph[vertex][i] && !visited[i]) {
            DFS(i);
        }
    }
}

5. 그래프 알고리즘

---

1. 최소 신장 트리 (MST)

모든 정점을 연결하는 최소 비용의 트리.
크루스칼 알고리즘: 간선을 정렬 후 최소 비용 간선을 선택.
프림 알고리즘: 정점 집합에서 최소 비용 간선을 선택하며 확장.

2. 최단 경로 알고리즘

다익스트라 알고리즘: 단일 출발점에서 모든 정점까지 최단 경로.
벨만-포드 알고리즘: 음의 가중치 간선이 있는 그래프에서 최단 경로.
플로이드-워셜 알고리즘: 모든 정점 쌍 간 최단 경로.

3. 위상 정렬

유향 비순환 그래프(DAG)의 순서를 결정.
작업 스케줄링과 같은 의존성 문제를 해결.

6. 그래프의 활용

---

• 네트워크 분석: 데이터 트래픽 경로 최적화.
• 소셜 네트워크: 사용자 간 관계 분석.
• 지도 및 경로 탐색: 최단 경로 찾기 (Google Maps).
• 컴퓨터 비전: 이미지 분할.
• 작업 스케줄링: 프로젝트의 의존성 관리.

7. 그래프의 장단점

---

장점

• 복잡한 관계를 직관적으로 표현 가능.
• 네트워크, 경로 탐색 등 다양한 문제에 활용 가능.

단점

• 메모리 사용량이 많음.
• 복잡한 구현이 필요할 수 있음.