인접 행렬
-
그래프_구현하기카테고리 없음 2021. 4. 29. 15:43
그래프 구현하기 그래프를 구현하는 방법은 크게 2가지로 나누어 알아보자. 1. 그래프의 노드를 구현하는 방법 - 배열 또는 동적 배열 => 파이썬의 리스트로 구현이 가능하다. - 해시 테이블 => 파이썬의 딕셔너리로 구현이 가능하다. 2. 그래프의 에지를 구현하는 방법 - 인접 행렬 - 인접 리스트 먼저, 그래프의 노드를 구현하는 방법이다. 1. 동적 배열 / 파이썬 리스트 구현 방법 그래프는 노드라는 기본 데이터 단위를 가지며 리스트의 요소로 단순 값이 아닌 노드 자체를 요소로 하는 리스트를 만드는 방법이다. 이때 노드는 특정 인덱스 값을 부여받는데, 인덱스를 이용해 리스트의 O(1)으로 효율적인 접근이 가능하며, 노드 안의 인스턴스에 대한 접근도 그만큼 효율적으로 할 수 있게 되는 것이다. class..