2025-07-30 22:13

Tags:자료구조

그래프

• 정점(노드)과 간선]으로 이뤄진 비선형 구조

• 간선은 방향 있을수도 없을 수도 있음

• 간선은 가중치를 가질수도 있음

• 싸이클은 있을 수도 없을 수 도 있음

• 정점 집합 V (데이터 단위, 개체)

• 간섭집합 E (정점간의 연결관계)

표현 방식

인접 행렬 Adjacency Matrix

• V * V 이차원 배열
• 간선 존재 여부 또는 가중치 저장
• 간선 검사가 O(1)으로 매우 빠름
• 메모리 비효율적
• 공간 복잡도를 높인 대신 시간 복잡도 낮춤

인접 리스트 (Adjacency List)

• V 배열
• 각 원소에 연결된 정점 리스트 저장
• 메모리 효율적
• 순회 효율적
• 간선 검사 O(deg(v)) 로 오래걸림
• 공간 절약 한 대신 시간 복잡도 올라감

기본 연산

4. 기본 연산

• 정점 추가 제거
• 간선 추가 제거
• 인접 확인 및 반환
• 반환

너비 우선 탐색 과 깊이 우선 탐색 에 핵심적으로 사용

References

트리 그래프 자료구조 핸드북 요약 그래프 자료구조 심화_ 파이썬 구현 가이드