[크래프톤 정글] 그래프 개념

그래프(데이터 구조에서의 그래프)는 노드(정점)와 엣지(간선)로 이루어진 비선형 자료구조로, 다양한 문제를 해결하는 데 사용된다. 그래프는 서로 연결된 데이터 간의 관계를 표현하기에 유용하다. 이를 통해 다양한 알고리즘이 적용될 수 있으며, 특히 네트워크, 소셜 미디어 분석, 경로 탐색 등에서 자주 사용된다.

1. 그래프의 기본 요소

• 노드(Node, 정점): 데이터 포인트를 의미한다. 그래프에서는 보통 원으로 표시되며, 각 노드는 고유한 값을 가진다.
• 엣지(Edge, 간선): 노드 간의 연결을 의미한다. 두 노드 사이의 관계를 나타내며, 방향성 여부에 따라 유향 그래프와 무향 그래프로 나뉜다.

2. 그래프의 종류

1. 무향 그래프(Undirected Graph)

• 예시: 노드 A와 노드 B가 있고, 이 둘을 연결하는 엣지가 존재한다. 엣지에는 방향이 없으며, A와 B는 서로 연결되어 있다.

  A -- B

2. 유향 그래프(Directed Graph)

• 예시: 노드 A에서 노드 B로 향하는 유향 엣지가 있다. 엣지에는 방향이 표시되어 있으며, A에서 B로의 경로만 가능하다.

  A -> B

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

• 예시: 노드 A, B, C가 있으며, 이들 사이의 엣지에는 각기 다른 가중치가 부여되어 있다. 예를 들어, A에서 B로의 엣지에는 3이라는 가중치가 있고, B에서 C로의 엣지에는 2라는 가중치가 있다.

  A -3-> B -2-> C

4. 완전 그래프(Complete Graph)

• 예시: 노드 A, B, C가 있으며, 이들 각각은 다른 모든 노드와 연결되어 있다. 즉, 각 노드 간에 엣지가 존재한다.

  A -- B
   \  /
    C

5. 이분 그래프(Bipartite Graph)

• 예시: 두 개의 노드 집합이 있다. 집합 1에는 노드 A와 B가 있고, 집합 2에는 노드 C와 D가 있다. 집합 1의 노드들은 집합 2의 노드들과만 연결되며, 같은 집합 내에서는 연결되지 않는다.

  A    C
   \  /
    B    D

3. 그래프의 표현 방법

• 인접 행렬(Adjacency Matrix): 그래프를 2차원 배열로 표현하는 방식이다. 노드 간의 연결을 0과 1로 나타내며, 가중치 그래프의 경우 가중치를 나타낼 수 있다.

  예:

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

• 인접 리스트(Adjacency List): 각 노드와 연결된 노드들을 리스트로 표현하는 방식이다. 공간 효율성이 높아 큰 그래프에 적합하다.

  예:

  A: B, D
  B: A, C
  C: B, D
  D: A, C

• 엣지 리스트(Edge List): 간선 자체를 리스트로 표현하는 방식이다. 각 간선이 연결된 두 노드와 가중치를 포함할 수 있다.

  예:

  (A, B), (A, D), (B, C), (C, D)

4. 그래프 탐색 알고리즘

• 깊이 우선 탐색(DFS, Depth-First Search): 그래프의 한 노드에서 출발하여 한 경로를 따라갈 수 있는 한 끝까지 가는 탐색 방법이다. 재귀적 혹은 스택을 이용해 구현할 수 있다.

• 너비 우선 탐색(BFS, Breadth-First Search): 그래프의 한 노드에서 출발하여 인접한 노드들을 먼저 탐색하고, 그 다음 인접한 노드들을 탐색하는 방식이다. 큐를 이용해 구현할 수 있다.

5. 그래프 관련 알고리즘

• 최단 경로 알고리즘:

  • 다익스트라 알고리즘: 가중치가 있는 그래프에서 한 노드에서 다른 모든 노드로의 최단 경로를 찾는 알고리즘이다.
  • 벨만-포드 알고리즘: 음의 가중치를 포함하는 그래프에서 최단 경로를 찾는 알고리즘이다.
  • 플로이드-워셜 알고리즘: 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘으로, 동적 계획법을 사용한다.

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

  • 크루스칼 알고리즘: 간선을 하나씩 추가하면서 트리를 구성하는 알고리즘으로, 간선의 가중치를 기준으로 정렬한 후 순차적으로 선택한다.
  • 프림 알고리즘: 하나의 시작 노드에서 출발하여 트리를 확장해 나가는 방식으로, 가장 비용이 적은 간선을 선택한다.

6. 그래프의 활용 예

• 네트워크: 네트워크 토폴로지에서 노드는 장치(컴퓨터, 라우터 등), 엣지는 연결(케이블, 무선 링크)을 나타낸다.
• 소셜 네트워크: 노드는 사람(사용자)을, 엣지는 사용자 간의 관계(팔로우, 친구)를 나타낸다.
• 경로 탐색: 지도에서 장소(노드)와 길(엣지)를 연결하여 최단 경로를 찾는 데 사용된다.
• 웹 크롤링: 웹페이지(노드)와 하이퍼링크(엣지)를 그래프로 표현하여 효율적으로 탐색한다.

그래프는 데이터 구조의 핵심 개념 중 하나이며, 다양한 실제 문제를 해결하는 데 필수적인 도구로 사용된다.