반응형 Data structure1 [자료구조] 인접행렬 과 인접리스트 📘 자료구조 노트 그래프관련 문제를 풀 때 문제에 조건에 맞게 그래프를 구현하고 푸는게 일반적입니다. 이 때, 그래프의 연결관계를 나타내는 두 가지 방식이 있습니다. 인접행렬 이와 같은 그래프가 있다고 했을 때 인접 행렬은 다음과 같은 대칭 행렬 형태로 표현됩니다. 그러므로 꼭짓점의 개수를 n이라고 할 때 인접 행렬은 O(n^2)의 공간 복잡도 를 갖습니다. 인접행렬의 특징 원소에 접근하는데 걸리는 시간이 상수 시간(1)이라면 꼭짓점 i에서 j로 가는 변이 있는지를 상수 시간에 알 수 있습니다.(O(1)) 하지만, 그래프에 존재하는 모든 간선의 수는 O(n^2) 안에 알 수있습니다. 인접 리스트 이와 같은 그래프가 있다고 했을 때 인접 그래프는 다음과 같은 연결 리스트로 표현됩니다. 꼭지점의 개수를 n .. 2023. 3. 26. 이전 1 다음 반응형
