비선형 자료구조 - 그래프

비선형 자료구조

- 순차적으로 나열되는 것이 아닌 앞,뒤의 관계가 1:N, N:N인 자료구조

ex. 그래프, 트리

 

 

왜 비선형 자료구조를 사용할까?

- 더 많은 정보를 담고

- 많은 정보를 담은 상태에서 더 빨리 탐색하기 위함

 

 

그래프

- 노드(정점) + 간선 으로 연결관계를 표현하는 자료구조

 

---

그래프 특징

 

1. 방향성

- 간선에 방향성 추가 (기존 A - B, 방향성 추가 A -> B )

방향 그래프

- 방향성이 추가되면서 한 쪽 방향으로의 접근만 가능해짐

- 해당 연결성을 확인하기 위해 Floyd - Warshall 알고리즘 활용

 

2. 가중치

- 간선에 가중치(비용) 추가

- 가중치 + 방향 성분이 모두 포함된 그래프 -> 네트워크

- 가중치 개념이 추가되면서 기존에 없던 minimum cost 를 확인해야하는 문제 발생 -> 최소 비용에 대한 고민

- 해당 고민을 Dijkstra를 활용하여 해결

 

3. 연결성

연결 그래프(좌), 비연결 그래프(우)

 

4. 순환

순환

- 방문했던 노드를 다시 방문 O

비순환

- 방문했던 노드를 다시 방문 X

 

---

그래프 구현 방법

 

1. 인접행렬 

- 그래프의 정점들을 행과 열로 나타내고, 정점 간의 연결 여부를 행렬의 원소로 표현하는 방법

- 만약 정점 i와 정점 j가 간선으로 연결되어 있다면, matrix[i][j]에 1(또는 가중치)을 저장하고, 연결되어 있지 않다면 0을 저장

 

 

 

2. 인접리스트

- 인접 리스트는 각 정점에 대해 연결된 정점들의 목록을 저장하는 방법

- 보통 배열이나 리스트를 사용하여 각 정점마다 연결된 정점들을 별도의 리스트로 관리

 

---

그래프 탐색 방법

그래프 탐색은 그래프 내의 모든 정점(Vertex)을 방문하고, 정점 간의 관계를 파악하는 과정

 

1. BFS

- BFS는 시작 정점에서 가까운 정점부터 먼저 방문하는 탐색 방법

- 주로 큐(Queue)를 사용하여 구현하며, 레벨 단위로 정점을 탐색

2. DFS

- DFS는 시작 정점에서 가능한 한 깊게 탐색한 후, 더 이상 진행할 수 없게 되면 이전 정점으로 돌아와서 다른 경로를 탐색하는 방식

- 주로 스택(Stack) 또는 재귀(Recursion) 사용하여 구현