[ch 14] 그래프_1(개념과 종류)

[주제]

- 그래프의 개념과 종류

- 구현 모델

[정의]

- 정점(Vertex) 사이에 간선(Edge)이 연결된 형태의 자료구조

- 정점: 연결의 대상이 되는 개체 또는 위치

- 간선: 정점 사이를 연결하는 선

■ 그림(기본 그래프의 종류)

※ 연락을 돌리는 컨셉을 기준으로 설명

- 무방향 그래프(Undirected Graph): 연결 관계에 있어서 방향성이 없는 그래프

- 연락의 시작이 '만수'일 경우 만수는 '나나', '길동'에게 연락할 수 있음

- 나나는 '포포'에게 연락할 수 있음

- 길동은 '포포', '김민', '철수'에게 연락할 수 있음

- 중간에 연락이 끊겨서 다수의 사람이 연락을 받지 못할 확률이 매우 낮음

- 방향 그래프(Directed Graph): 간선에 방향정보가 포함된 그래프. 또는 다이그래프(Digraph)라고 함

- 연락의 시작이 '길동'일 경우 '포포→나나→만수→길동' 순서로 연락하여 연락이 1차 완료를 확인.

  '철수→김민→길동' 순서로 또 연락하여 최종 연락을 확인

  ※ '포포'부터 시작 또는 '철수'부터 시작 순서는 상관없음

[완전 그래프(Complete Graph)]

- 각각의 정점에서 다른 모든 정점을 연결한 그래프

- 방향성이 있을 경우 무방향에 비해 간선 수가 2배가 됨

[가중치 그래프(Weight Graph)]

- 간선에 가중치 정보가 존재

- 가중치는 두 정점 사이의 '거리', 두 정점을 이동하는데 걸리는 '시간'과 같은 정보가 될 수 있음

- 'A'에서 'C'로 이동하는 빠른 길을 찾을 경우 'A → B → C'가 됨

  ※ 가중치가 이동에 걸리는 시간이라고 가정

[부분 그래프(Sub Graph)]

- 부분 집합이 원 집합의 일부 원소로 이루어진 집한인 것처럼, 

  부분 그래프는 원 그래프트의 일부 정점 및 간선으로 이뤄진 그래프를 뜻함

■ 그림(그래프의 집합 표현)

- 그래프는 정점과 간선의 집합

- 집합의 표기법을 이용해서 표현이 가능

- 그래프의 '정점' 집합 = V(G)

- 그래프의 '간선' 집합 = E(G)

- V(G1) = {A, B, C, D}        E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}

- V(G2) = {A, B, C, D}        E(G2) = {(A, C), (A, D), (B, C)}

※ 반대되는 경우는 동일하므로 미표기. 예) A, B = B, A

- V(G3) = {A, B, C, D}        E(G3) = {<A, B>, <A, C>, <D, A>}

- V(G4) = {A, B, C, D}        E(G4) = {<A, C>, <B, C>, <D, A>}

---

[구현 모델]

1. 인접 행렬(Adjacent Matrix) 기반 그래프: 정방 행렬을 활용

- 정방 행렬은 가로세로의 길이가 같은 행렬을 의미

■ 그림(인접 행렬)

- 정점이 '4개'면 가로세로의 길이가 '4'인 2차원 배열을 선언

- 두 정점이 연결되어 있으면 '1'로, 연결되어 있지 않으면 '0'으로 표시

- 무방향의 경우 간선에 방향성이 없기 때문에 하나의 간선에 대해서 두 개의 지점을 '1'로 표시

- 무방향과는 대칭적이지 않다는 것만 다름

2. 인접 리스트(Adjacent List) 기반 그래프: 연결 리스트를 활용

■ 그림(인접 리스트)

- 각 정점 별로 가리키는 정점의 정보만을 연결 리스트에 저장