[알고리즘] 그래프(Graph) - 가중치, 인접행렬, 인접리스트

그래프(Graph)는 정점(Vertex)과 간선(Edge) 으로 이루어진
데이터간의 연결 관계를 표현한 자료구조이다.
 
트리가 계층 구조를 표현하고 있다면
그래프는 객체들의 관계를 표현하는데 사용된다.
 
예를 들어 지하철 노선도, 길찾기 시스템등은 모두 그래프로 표현할 수 있는 예시이다.
 
즉, 트리는 위에서 아래로 뻗어나가는 구조를 유지해야 하지만
그래프는 점과 점이 서로 연결되어 있어
트리보다는 좀 더 자유롭게 연결된다라고 생각하면 된다.

---

💡 트리와 그래프의 차이

트리는 그래프의 한 종류에 속한다.
하지만 트리는 계층 구조를 표현하기 위해 몇가지 제한 조건을 가진 그래프라 생각하면 된다.

구분	트리	그래프
구조	계층 구조	연결 구조
방향	부모 → 자식 관계	자유로운 연결
사이클	없음	가능
루트 노드	존재	없을 수 있음
예시	폴더구조, 조직도	지도, 네트워크

---

1. 그래프의 구성요소

1_1) 정점 (Vertex)

그래프에서 데이터를 저장하는 하나의 노드를 의미한다.
지하철 노선도로 생각하면 각각의 역 하나가 정점이 되는것과 같다.

---

1_2) 간선 (Edge)

정점과 정점을 연결하는 선을 의미한다.
지하철 노선도에서 역과 역 사이를 연결하는 구간이 간선이 된다.

강남역 -------- 역삼역 -------- 선릉역

# 강남역 ↔ 역삼역 사이 연결
# 역삼역 ↔ 선릉역 사이 연결

---

1_3) 인접 정점 (Adjacent Vertex)

인접 정점은 간선으로 직접 연결되어 있는 정점을 의미한다.

강남역 -------- 역삼역 -------- 선릉역

위 지하철 노선도를 기준으로 보면
중간 과정을 거치지 않고 바로 이동할 수 있는 역을 말한다.
 

• 강남역과 역삼역 → 인접 정점
• 역삼역과 선릉역 → 인접 정점
• 강남역과 선릉역 → 직접 연결되어 있지 않기 때문에 인접 정점 X

---

1_4) 가중치 (Weight)

가중치는 간선에 부여되는 값 또는 비용을 의미한다.
일반적인 그래프의 경우 정점끼리 연결되어 있는지만 표현하고 끝나지만
가중치를 사용하면 단순한 연결관계만 표현하는것이 아닌
이동하는데 필요한 비용까지 함께 표현이 가능하다.

        2분           3분

강남역 ------- 역삼역 ------- 선릉역

# 강남역 → 역삼역 : 가중치 2
# 역삼역 → 선릉역 : 가중치 3
# 강남역 → 역삼역 → 선릉역 : 2 + 3 = 5 : 가중치 5

실제로 지하철 이동시간, 택시의 이동비용과 같이 목적에 따라 다른 값을 가중치에 사용한다.
 

💡 가중치는 항상 거리를 의미할까?

가중치는 늘 실제 거리를 의미하진 않는다.
그래프에서 무엇을 기준으로 최적의 경로를 찾을지에 따라 매번 의미가 달라진다.
 
지도어플에서 길찾기는 거리가 가중치가 되고, 택시를 타고 이동할땐 요금이 가중치,
네트워크를 예시로 보면 데이터를 전송하는데 드는 비용이 가중치가 된다.
 

❓ 왜 가중치가 필요할까?

단순 그래프에선 연결 여부만 확인하기 때문에 두 경로가 있을 때 어떤 경로가 더 좋은지 판단하기 어렵다.
 
예를 들어 강남역에서 선릉역까지 이동한다 했을 때 지하철과 택시 두가지 경로가 있다 가정하면
두 방법 모두 강남역에서 선릉역까지 이동은 하지만 필요한 시간은 다르다.

가중치가 없다면 연결여부만 확인하기 때문에 택시처럼 바로 연결된 경로가 더 좋아보일 수 있지만
이동시간을 가중치로 저장하여 경로에 필요한 비용을 계산해보면 오히려 지하철이 더 효율적이다.

즉, 이동 횟수는 지하철이 더 많지만 가중치의 합은 지하철이 더 적기 때문에 더 효율적인 경로라 판단하는 것이다.
이와 같이 가중치는 비용을 기준으로 최적의 경로를 찾기 위해 사용된다.

---

2. 그래프의 종류

2_1) 방향 그래프 (Directed Graph)

간선에 방향이 있는 그래프로 SNS 팔로우 관계를 생각하면 된다.

A → B

A 에서 B로 이동할 수 있지만 반대로 B에서 A로 이동할 수 있는것은 아닌 구조이다.

---

2_2) 무방향 그래프(Undirected Graph)

간선에 방향이 없는 그래프로 친구 관계를 생각하면 쉽다.

A ↔ B

 A에서 B, B에서 A 양쪽 모두 이동할 수 있는 구조이다.

---

2_3) 가중 그래프(Weighted Graph)

간선에 가중치가 추가된 그래프로
각 연결마다 비용(가중치)가 존재하며, 최단 거리 알고리즘에서 많이 사용된다.

 10
A → B

  3
B ↔ C

---

3. 그래프의 표현 방법

3_1) 인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원의 배열을 이용해서 연결 여부를 표현하는 방법이다.

3_1_a)인접 행렬의 장단점

👍 인접 행렬의 장점

• 두 정점의 연결 여부 빠른 확인 가능
• 시간복잡도 O(1)

👎 인접 행렬의 단점

• 연결되지 않은 정보도 함께 저장해야 함
• 메모리 사용량이 많아짐

---

3_2) 인접 리스트(Adjacency List)

인접 리스트는 리스트를 이용하여 연결된 노드만 저장하는 방법으로

 

3_2_a)인접 리스트의 장단점

👍 인접 리스트의 장점

• 연결된 데이터만 저장가능
• 메모리 효율이 좋음

👎 인접 리스트의 단점

• 특정 두 정점이 연결되어있는지 확인하기 위해선 별도로 탐색이 필요