자료구조 시리즈 9편

그래프(Graph) 완전 이해하기

이전 글에서는 트리(Tree)에 대해 알아봤습니다.
이번에는 복잡한 관계를 표현하는 자료구조, 그래프(Graph) 에 대해 자세히 정리해봅니다.

---

1. 그래프란?

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다.

• 정점(Vertex): 데이터의 단위 (노드라고도 함)
• 간선(Edge): 정점과 정점을 연결하는 선
• 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)가 있음

---

2. 그래프의 기본 용어

용어 설명

정점(Vertex)	데이터를 저장하는 노드
간선(Edge)	두 정점을 연결하는 선
인접(Adjacent)	두 정점이 간선으로 직접 연결된 관계
차수(Degree)	정점에 연결된 간선의 수
경로(Path)	정점들을 순서대로 따라간 길
사이클(Cycle)	시작 정점으로 다시 돌아오는 경로

---

3. 그래프 표현 방법

방법 설명

인접 행렬(Adjacency Matrix)	2차원 배열로 정점 간 연결 여부 표시
인접 리스트(Adjacency List)	각 정점마다 연결된 정점 리스트 저장

 인접 행렬 예시

int[,] graph = new int[4, 4]
{
    {0, 1, 0, 0},
    {1, 0, 1, 1},
    {0, 1, 0, 1},
    {0, 1, 1, 0}
};

 인접 리스트 예시

using System.Collections.Generic;

List<int>[] graph = new List<int>[4];
for (int i = 0; i < 4; i++)
{
    graph[i] = new List<int>();
}

graph[0].Add(1);
graph[1].Add(0); graph[1].Add(2); graph[1].Add(3);
graph[2].Add(1); graph[2].Add(3);
graph[3].Add(1); graph[3].Add(2);

---

4. 실생활 예시로 이해하기

• 그래프 = 지하철 노선도
  • 각 역(정점)이 노선(간선)으로 연결됨
• 그래프 = 소셜 네트워크
  • 사용자(정점)와 친구 관계(간선)를 표현

---

5. 그래프의 활용 사례

사용 예시 설명

네트워크 경로 찾기	인터넷 라우팅, 네트워크 최단 경로 탐색
소셜 네트워크 분석	친구 추천, 커뮤니티 분석
지도 및 내비게이션	최단 거리, 최단 시간 경로 탐색

---

이번 글에서는 그래프(Graph) 의 개념, 기본 용어, 표현 방법, C# 코드 예시를 정리했습니다.

• 정점과 간선으로 다양한 관계를 표현
• 인접 행렬과 인접 리스트로 그래프 구현 가능
• 네트워크, 소셜 미디어, 지도 등 다양한 분야에서 활용