2025-07-30 22:13
Status:
Tags:자료구조
그래프
-
정점과 간선으로 이뤄진 비선형 구조
-
간선은 방향 있을수도 없을 수도 있음
-
간선은 가중치를 가질수도 있음
-
싸이클은 있을 수도 없을 수 도 있음
-
정점 집합 V (데이터 단위, 개체)
-
간섭집합 E (정점간의 연결관계)
표현 방식
인접 행렬 Adjacency Matrix
- V * V 이차원 배열
- 간선 존재 여부 또는 가중치 저장
- 간선 검사가 O(1)으로 매우 빠름
- 메모리 비효율적
- 공간 복잡도를 높인 대신 시간 복잡도 낮춤
인접 리스트 (Adjacency List)
- V 배열
- 각 원소에 연결된 정점 리스트 저장
- 메모리 효율적
- 순회 효율적
- 간선 검사 O(deg(v)) 로 오래걸림
- 공간 절약 한 대신 시간 복잡도 올라감
기본 연산
- 정점 추가 제거
- 간선 추가 제거
- 인접 확인 및 반환
- 반환
너비 우선 탐색 과 깊이 우선 탐색 에 핵심적으로 사용