그래프

• 정점(V)과 간선(E)의 집합으로 이루어진 비선형 자료구조이다.
• 정점은 노드라고도 불리고, 간선은 노드들을 연결시켜주는 선이다.

• 그래프의 표현식: G(E,V).

• 노드: 데이터를 담고 있는 객체(?)

예시) 페이스북

• 페북에는 사용자, 사진, 영상, 그룹, 페이지, 댓글 등 많은 요소가 있고, 각각의 요소는 데이터를 담고 있는 노드이다.
• 사용자가 사진을 게시하거나, 댓글을 작성하거나, 다른 사용자와 친구가 된다면 이들 노드들은 간선으로 연결이 된다.

종류

Directed graph(유향 그래프): (v,u) 간선이 존재해도 반대의 (u,v) 간선은 존재하지 않을 수도 있는 그래프. 간선의 방향은 화살표로 표현.
Undirected graph(무향 그래프): (v,u) 간선이 존재한다면 반대의 (u,v) 간선도 존재하는 그래프.

V = { 0, 1, 2, 3 }
E = { (0, 1), (0, 2), (0, 3), (1, 2) }
G = { V, E }

용어

• Adjacency(인접): 간선으로 이어진 정점.
  위 예시에서 2와 3은 인접 정점이 아니다.
• Path(경로): 한 정점에서 다른 정점으로 가는 수열.
  (0-1, 0-2)와 (0-2)는 모두 0에서 2로 가는 경로에 해당된다.
• Closed Path(폐쇄 경로): 한 정점이 경로의 시작점이자 끝점인 경로.
• Cycle: 경로 내에 중복된 정점(시작점,끝점 제외) 혹은 간선이 없는 경로.

구현 방법

인접 행렬

위의 그래프를 아래와 같이 2차원 배열로 구현할 수 있다.
이 2차원 배열을 인접 행렬이라고 한다.

위 그래프는 무향 그래프(쌍방)이기 때문에 (0,2)와 (2,0) 모두 표시해줘야 한다.

장점

• 간선 탐색이 매우 빠름
  *Edge lookup(간선 탐색): 정점A와 정점B 사이의 간선 탐색

단점

• 모든 경우의 수(위의 경우 4x4)를 미리 초기화해야 하므로 공간을 많이 차지함

인접 리스트

다른 구현 방식으로는 연결리스트의 배열이 있다.
이 연결리스트의 배열을 인접 리스트라고 한다.

장점

• 인접 행렬과는 다르게 필요한 값(존재하는 가선)만 저장할 수 있음.

연산

그래프의 가장 자주 쓰이는 연산은 아래와 같다.

1. 특정 요소(정점 혹은 간선)가 있는지 확인
2. 그래프 탐색 (DFS, BFS)
3. 요소(정점 혹은 간선) 삽입
4. 한 정점에서 다른 정점으로의 경로 구하기

심화

Spanning Tree

• 신장 트리는 무향 그래프의 부분집합으로, 모든 정점들이 최소한의 간선 갯수로 연결되어있는 그래프를 뜻한다.
• 그래프의 모든 정점들에 간선이 존재한다면 신장 트리가 최소 한 개 있다는 뜻이며, 한 그래프 내에 여러 개의 신장 트리가 존재할 수 있다.
• 신장 트리에 정점이 n개가 존재한다면 간선은 n-1개 있어야 한다.
  

예를 들면 위 그래프에서 굵은선으로 이루어진 그래프가 신장 트리 중 하나이다.

Minimum Spanning Tree

• 최소 신장 트리는 간선들에 가중치가 정해져있을 때 가장 작은 비용으로 이루어질 수 있는 신장 트리를 뜻한다.

• 대표적인 알고리즘으로는 Kruskal 알고리즘, Prim 알고리즘이 존재한다.

최단 경로

• 최단 경로는 간선들에 가중치가 정해져있을 때 한 정점에서 다른 정점으로의 경로의 비용이 가장 작은 경로를 뜻한다.
• 주로 가중치가 있는 유향 그래프에서 나타나지만 무향 그래프에도 적용이 가능하다.

• 현실 세계에서는 지도에 최단 경로 구하기를 적용할 수 있다. 다양한 최단 경로 알고리즘으로 네비게이션 동작을 최적화할 수 있다.

• 2가지 대표적인 최단 경로 알고리즘으로는

  • Dijkstra's Shortest Path Algorithm (다익스트라)
  • Bellman Ford's Shortest Algorithm (벨만 포드)

  가 있다.

사용처

1. 네트워크 및 통신

   • 컴퓨터 네트워크, 인터넷, 라우팅 알고리즘 등과 같은 통신 시스템의 구조를 모델링하는 데 사용된다.
   • 노드는 라우터, 서버, 컴퓨터 등의 네트워크 장치를 나타내고, 간선은 연결과 통신 경로를 나타낸다.

2. 소셜 네트워크 분석

   • 소셜 네트워크 분석에서 사용되어 친구 관계, 연결, 그룹 구성 등을 모델링한다.
   • 사용자, 프로필 또는 개인 간의 상호 작용은 그래프의 노드와 간선으로 표현될 수 있다.

3. 경로 및 최적화 문제

   • 경로 찾기, 최단 경로 문제, 여행자 문제 등과 같은 경로 및 최적화 문제를 해결하는 데 사용된다.
   • 최소 신장 트리, 최단 경로 알고리즘, 플로우 네트워크 등 그래프 기반의 알고리즘을 활용한다.

4. 데이터베이스 및 검색 엔진

   • 관계형 데이터베이스 및 검색 엔진에서 사용되어 데이터 사이의 관계와 연결성을 모델링한다.
   • 그래프 데이터베이스는 복잡한 관계와 네트워크를 저장하고 조회하는 데 사용된다.

알고리즘 문제

1. 최단 경로 문제 (Shortest Path Problem)

   • 두 정점 간의 최단 경로를 찾는 문제
   • 대표적인 알고리즘: Dijkstra 알고리즘, Bellman-Ford 알고리즘.

2. 최소 신장 트리 (Minimum Spanning Tree)

   • 가중치가 있는 그래프에서 모든 정점을 연결하면서 간선의 가중치 합이 최소인 트리를 찾는 문제.
   • 대표적인 알고리즘: Kruskal 알고리즘, Prim 알고리즘.

3. 너비 우선 탐색 (Breadth-First Search, BFS)

   • 그래프에서 한 정점으로부터 모든 정점을 탐색하는 알고리즘.
   • 너비 우선 탐색은 그래프의 최단 경로 문제, 연결성 확인, 그래프 구조 분석 등에 사용.

4. 깊이 우선 탐색 (Depth-First Search, DFS)

   • 그래프에서 한 정점으로부터 가능한 한 깊숙이 들어가서 탐색하는 알고리즘.
   • 깊이 우선 탐색은 사이클 검사, 연결 구성 요소 확인, 위상 정렬 등에 활용.

5. 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)

   • 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘.
   • 음의 가중치를 허용하는 그래프에서도 적용 가능.

6. 위상 정렬 (Topological Sorting)

   • 방향 그래프에서 각 정점의 선행 순서를 유지하면서 정점들을 정렬하는 알고리즘.
   • 주로 작업의 의존 관계를 해결하는 데 사용.

7. 강한 연결 요소 (Strongly Connected Components)

   • 방향 그래프에서 강하게 연결된 정점들의 최대 집합을 찾는 문제.
   • 대표적인 알고리즘: Kosaraju's 알고리즘, Tarjan's 알고리즘.