CS/자료구조
[자료구조] 비선형 자료구조 2탄 : 그래프
개발중인 감자
2023. 8. 12. 15:04
1. 그래프의 개념
정점과 간선으로 이루어진 자료구조이다. 트리도 일종의 그래프이다.
하지만 트리와는 다르게 루트 노드, 부모와 자식이라는 개념이 존재하지 않으며 네트워크 모델 즉 객체와 이에 관계를 나타내는 방식이다.
간선의 방향성에 따라 무방향 그래프 혹은 방향 그래프로 나눌 수 있다.
📌 그래프의 용어들
정점, 노드 : 데이터가 저장되는 곳
간선 : 노드간의 관계
차수 : 무방향 그래프에서 하나의 정점에서 인접한 간선의 수
진출 차수 : 방향 그래프에서 한 노드에서 외부로 향하는 간선의 수
진입 차수 : 방향 그래프에서 외부에서 한 노드로 들어오는 간선의 수
📌 그래프 표현 방식
1) 인접 행렬
무방향 그래프를 기준으로 1과 3인 정점이 연결되어있다면, graph[1][3] = graph[3][1] = 1 로 표현할 수 있다.
2) 인접 리스트
인접행렬과 비교했을 때, 정점이 많고 간선이 상대적으로 적은 상태에서 공간을 절약할 수 있는 방법이다.
인접행렬은 V개의 정점에 대해 O(V²)의 공간이 필요하고, 인접리스트는 E개의 간선이 더해져 O(V+E)의 공간이 필요하다.
| 인접행렬 | 인접리스트 | |
| 공간 복잡도 | O(V²) | O(V+E) |
| 정점 u,v 연결 여부 확인 시간 복잡도 | O(1) | O(min(degree(u), degree(v)) |
| 정점 v와 연결된 모든 정점 확인 시간 복잡도 | O(v) | O(degree(v)) |
| 효율적인 상황 | 두 점의 연결 여부를 자주 확인하거나, E가 V²에 가까울 때 |
특정 정점에 연결된 모든 정점을 자주 확인할 때나, E가 V²보다 훨씬 작을 때 |
출처 : 바킹독님의 블로그
2. 그래프의 탐색
📌 깊이 우선 탐색 DFS
갈 수 있는 만큼 최대 깊이로 들어가고, 더 이상 길이 없다면 이전 정점으로 돌아가는 방식으로 순회하는 방법.
재귀방식 혹은 스택을 이용해 구현한다.
📌 너비 우선 탐색 BFS
시작 정점에서 인접한 정점들을 우선으로 방문하고, 방문했던 정점에 대해 다시 인접한 정점들을 방문하며 순회하는 방식.
시작정점에 가까운 정점일 수록 먼저 방문하는 것이 특징이다. 보통 큐를 이용하여 구현할 수 있다.