Lecture 17 - Graph(1/4)

---

그래프

정점(vertex) 및 간선(edge)로 이루어진 자료구조이다.

G = (V, E) 형태로 나타냄 (V: 정점 집합, E: 간선 집합)

두 정점이 간선으로 연결되어 있을 경우 인접하다고 한다.

---

종류

그래프의 종류를 나누는 기준은 다음과 같다.

- 두 vertex 간 가능한 edge의 개수 

- Edge의 방향 유무

- Loop의 유무

- 추가적으로 edge의 weight 유무에 따라 weighted, unweighted로 나눌 수 있음

Weighted graph

Directed graph

가중치를 가진 유향 그래프

무향 그래프

가중치가 있는 무향 그래프

유향 그래프

가중치가 있는 유향 그래프

인접 행렬을 이용한 그래프의 표현은 이해하기 쉽고 간선의 존재 여부를 Θ(1)만에 파악 가능하다. 그러나 그래프 정보를 저장하기 위해서만 Θ(𝑛^2) 시간이 소요되고 메모리 사용량도 크다는 점은 단점으로 작용한다. 간선의 밀도가 높은 그래프에서는 인접 행렬을 사용한 표현이 적합하나, 정점의 수 대비 간선이 적은 경우에는 인접 행렬을 이용한 표현은 비효율적이다.

---

인접 리스트 (Adjacency list)

- N 개의 연결 리스트로 각 정점에서 시작하는 간선들을 표현

- i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓음

- 가중치 있는 그래프의 경우: 리스트에 가중치도 보관한다

 

인접 리스트는 메모리 사용량 측면에서는 인접 행렬보다 효율적일 수 있다. 그러나 특정 정점에 대해 이어진 간선을 검색하고자 하는 경우 worst case로는 Θ 𝑛 의 시간이 소 요될 수 있다. 따라서 인접 리스트 표현 방식은 간선의 밀도가 낮을 때 유용하다.

---

Graph traversal

Graph traversal은 목표 노드를 향해 그 경로의 노드들을 방문하는 과정이다.

Graph traversal 알고리즘에는 다양한 종류가 있습니다. 대표적인 알고리즘으로는 DFS(Depth First Search)와 BFS(Breadth First Search)가 있습니다. DFS는 깊이 우선 탐색으로, 한 노드에서 시작하여 그 노드와 연결된 모든 노드를 방문한 후에 다음 노드로 이동합니다. BFS는 너비 우선 탐색으로, 한 노드에서 시작하여 그 노드와 가장 가까운 노드부터 방문합니다.

 

 

BFS

 

 

DFS

 

---

신장 트리

트리는 싸이클이 없는 연결 그래프를 뜻하며 n개의 정점을 가진 트리는 항상 n-1개의 간선을 보유한다.

- 그래프 G의 신장 트리 (Spanning tree): 무향 연결 그래프에 대해 그래프 G의 정점들과 간선들로만 구성된 트리를 신장 트리라고 한다.

- 최소 신장 트리 (Minimum spanning tree): 신장 트리들 중 간선의 합이 최소인 신장 트리를 의미한다.

---