[데이터 구조와 활용] 그래프

1. 그래프

(1) 그래프 : 정점과 간선으로 구성된 비선형 데이터 구조

 - 현실 세계의 복잡한 연결 관계를 표현하는데 적합한 구조, 정점 간의 다양한 연결을 나타낼 수 있음

 [ 그래프 vs 트리 ]

  - 그래프 : 순환이 존재할 수 있고, 정점 간 연결 관계가 자유로움

  - 트리 : 그래프의 특수한 형태로, 순환이 없는 연결된 그래프임

(2) 그래프의 주요 용어

용어	설명
정점	그래프를 구성하는 각각의 원소
간선	정점과 정점을 연결하는 선
인접	두 정점이 간선으로 직접 연결된 상태
차수	특정 정점에 연결된 간선의 수
경로	한 정점에서 출발해 간선을 따라 다른 정점들로 이동하는 과정
순환	하나의 정점에서 출발하여 다시 출발 정점으로 돌아오는 경로 단, 적어도 하나 이상의 독립적인 간선을 포함해야 함
부분 그래프	원래 그래프에서 일부 정점과 간선만을 선택하여 만든 더 작은 그래프

(3) 그래프의 종류

 - 무방향 그래프 : 간선에 방향이 없는 그래프, 두 정점 사이가 쌍방향 연결을 의미

 - 방향 그래프 : 간선에 방향이 있는 그래프, 연결 관계가 단방향일 수 있음

 - 완전 그래프 : 모든 정점이 서로 직접 간선으로 연결된 그래프

 - 가중치 그래프 : 간선마다 비용, 거리 등의 값(가중치)를 가진 그래프

 - 이분 그래프 : 정점들을 정확히 두 개의 그룹으로 나누었을 때, 같은 그룹 내에선 연결이 전혀 없고 서로 다른 그룹 간에만 연결이 있는 그래프

 * 예시 : 회사와 구직자의 관계, 회사와 구직자로 두개의 그룹으로 나눠져 구직자들간의 연결은 없고, 회사와 구직자 사이에만 연결이 있음

 * 예시 : 소개팅 앱, 대학 수업 시간표 배정(강의실), 구직 활동 및 채용 플랫폼

 * 이처럼 이분 그래프는 서로 다른 두 개의 집단간의 연결을 분석하고 관리할 때 매우 유용하게 사용됨

 [ 이분 탐색의 이분 vs 이분 그래프의 이분 ]

 - 이분(Binary) : 데이터의 탐색 범위를 절반씩 나눈다는 의미로, 탐색 시간을 단축시키는 것이 목적임

 - 이분(Bipartite) : 정점 집합을 둘로 나눈다는 의미로 그래프의 구조를 분리하는 것이 목적임

(4) 그래프의 활용 사례

 - 무방향 그래프 : 친구 SNS 관계, 협력 네트워크 등

 - 방향 그래프 : 지하철 노선도, 일방 통행 도로

 - 완전 그래프 : 단체 대화방, 완전 연결 네트워크

 - 가중치 그래프 : 네비게이션, 항송편 노선도

 - 이분 그래프 : 구직자와 회사간의 매칭, 소개팅 앱

2. 그래프 표현

(1) 인접 행렬 : 2차원 배열로 그래프를 표현, 빠른 접근 속도가 장점

 - 정점이 많으면 메모리 낭비가 있을 수 있음

 - 2차원 배열을 이용하여 정점간의 연결 여부를 표현하는 방법

 - 배열의 값이 1이면 두 정점간 연결이 있고, 0이면 없음을 의미

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

g = [ [ 0, 1, 1], [1, 0, 1], [1, 1, 0]] print('A와 B의 연결 여부 : ' ,g[0][1]) print('A와 C의 연결 여부 : ' ,g[0][2]) print('C와 B의 연결 여부 : ' ,g[1][2])

(2) 인접 리스트 : 각 정점의 연결 정보를 리스트로 표현, 메모리 효율이 장점

 - 특정 간선 확인 시 시간이 더 걸릴 수 있다는 단점이 있음

 - 인접 리스트는 각 정점마다 연결된 다른 정점들을 리스트 형태로 저장

 - 연결된 간선이 많지 않은 경우 메모리를 매우 효율적으로 사용

 - 인접 리스트 예시

정점	연결된 정점 목록
A	B, C
B	A, C
C	A, B

g1 = {  'A' : ['B','C'], 'B' : ['A','C'], 'C':['B','C']} print('A와 연결된 정점들 : ' ,g1['A']) print('B와 연결된 정점들 : ' ,g1['B']) print('C와 연결된 정점들 : ' ,g1['C'])

3. 그래프 활용

(1) 그래프 탐색 : 그래프 안에서 연결된 정점들을 차례로 찾아보는 것을 말함

 - 깊이 우선 탐색, 너비 우선 탐색으로 나뉨

 - 연결관계 A-B, A-C, A-D, B-E, C-F, E-F, D-G인 그래프에서 두 가지 방식 확인

(2) 깊이 우선 탐색 : 출발점에서 한 방향으로 최대한 깊게 탐색한 후, 다른 방향을 탐색하는 방식

 - 미로 찾기, 연결된 구성요소 확인 시 유용

 - 시작점에서 가능한 깊게 탐색한 후 길이 막히면 이전으로 돌아와 다른 경로를 탐색

 - 탐색 순서 : A-B-E-F-C-D-G

(3) 너비 우선 탐색 : 출발점에서 가까운 정점을 우선적으로 방문하여 점차 범위를 넓히는 방식

 - 최단 경로 구할 때 주로 사용

 - 시작점에서 가까운 정점부터 방문하며 차츰 먼 정점으로 확장하며 탐색

 - 탐색 순서 : A-B-C-D-E-F-G

(4) 최소 신장 트리 : 가중치 그래프에서 모든 정점을 가장 적은 비용으로 연결하는 특별한 구조

 - 신장이란 모든 정점이 연결되어있다는 뜻이고, 최소 신장 트리는 말 그대로 모든 정점을 연결할 때 최소 비용(가중치의 합)으로 연결하는 구조를 의미

 - 최소 신장 트리는 순환이 없어야 함

 - 여러 도시를 연결할 때 도시간 도로의 건설비용을 최소로 하면서 모든 도시를 빠짐없이 연결해야하는 경우

(5) 크루스칼 알고리즘 : 간선을 오름차순으로 정렬 후 가장 작은 간선부터 차례로 선택하여 MST를 구성

 - 사이클이 발생하지 않는 간선만 선택

 - 모든 간선을 비용이 작은 순서대로 정렬

 - 비용이 작은 간선부터 선택하면서 순환이 생기지 않도록 연결

 - A-B > E-F > A-C > C-F > *제거 B-E > D-G > A-D

(6) 프림 알고리즘 : 임의의 정점에서 시작하여 비용이 가장 작은 간선을 선택하며 트리를 확장하여 MST를 만듦

 - 임시의 정점에서 시작

 - 연결 가능한 간선 중 순환이 생기지 않는 가장 비용이 작은 간선을 선택하여 하나씩 트리를 확장함

 - A-B > A-C > C-F > E-F > *제거 B-E > A-D > D-G

(7) 최단 경로 : 특정 시작 정점으로부터 다른 모든 정점까지 이동하는 데 필요한 비용이나 거리가 최소가 되는 경로를 찾는 문제

 - 가중치 그래프에서 특정 정점에서 다른 모든 정점까지의 최단거리를 찾는 데 사용

 - 다익스트라 알고리즘은 최단 경로를 찾는 대표저긴 알고리즘으로 그래프 탐색 개념을 활용해 두 정점 사이의 최소 비용 경로를 찾음

 [ 최소 신장 트리 VS 최단 경로 ]

 - 최소 신장 츠리 : 모든 정점을 최소 비용으로 연결하는 트리를 찾는 문제

 - 최단 경로 : 특정 시작 정점에서 모든 다른 정점까지 최소 비용의 경로를 찾는 문제  

 [ 너비 우선 탐색 VS 다익스트라 알고리즘 ]

 - 너비 우선 탐색 : 시작 정점에서 도착 정점까지 간선의 개수가 최소인 경로를 찾을 때 사용, 간선마다 거리가 모두 동일한 기준치로 가중치가 없는 그래프에서 사용됨

 - 다익스트라 알고리즘 : 시작 정점에서 도착 정점까지 각 간선마다 비용이 있을 때 그 비용을 최소화하는 경로를 찾는 알고리즘. 가중치 그래프에서 사용

(8) 다익스트라 알고리즘

 - 특정 시작 정점에서 모든 정점까지의 최단 거리를 찾는 방법임

 - 출발점에서 가장 가까운 정점을 선택하고 그 정점을 통해 다른 정점으로 가는 경로를 갱신

 - 초기에 출발지점(A) 기준 외의 정점을 무한대로 셋팅 A(0), B~G(무한대)

 - 단계별로 최단거리를 비교하여 확정 값을 넣음

 - (0, 2, 3, 6, 6, 6, 11) 결과로 저장