[Java] 그래프

1. 그래프 정점 간의 관계를 간선으로 표현한 것. 간선의 방향에 따라서 무향 그래프(양방향 그래프), 유향 그래프로 나뉠 수 있다. 밀집도에 따라서 완전 그래프, 밀집 그래프 그리고 희소 그래프로 나뉜다. 이 외에도 가중치 그래프, 사이클 없는 그래프 등 다양한 그래프가 존재한다. 그래프를 표현하는 방식은 크게 3가지 있다. 그래프 표현 방식 설명 시간 복잡도 (연결 여부 확인) 공간 복잡도 특징 인접 행렬 그래프의 노드들을 2차원 배열에 저장. 배열의 행과 열은 각각 그래프의 노드를 의미하며, 배열의 값은 두 노드 간의 간선 유무(또는 가중치)를 의미함. O(1) O(V^2) -구현이 쉽다. -진입 차수를 구하기 쉽다. -밀집 그래프에 유리한다. 인접 리스트 각 노드에 연결된 노드들을 리스트로 저장...

2024.02.25