그래프 메모리 구현

Question

메모리에서 그래프를 나타내는 데 일반적으로 사용되는 두 가지 방법은 인접성 목록 또는 인접성 매트릭스를 사용하는 것입니다. 인접 목록은 링크 된 목록에 대한 포인터의 배열을 사용하여 구현됩니다. 벡터 벡터를 사용하는 것보다 빠르다는 이유가 있습니까? 역 추적이 훨씬 더 간단하기 때문에 검색 및 순회를 더 빠르게 만들어야하는 것처럼 느껴집니다.

Answer 1

링크 된 인접성의 벡터는 실제로 많은 변형이있는 선호하는 교과서 밈입니다. 확실히 벡터 벡터를 사용할 수 있습니다. 차이점은 무엇입니까?

하나는 링크 (두 번 어쨌든 두 번)는 가장자리를 쉽게 추가하고 일정 시간 내에 삭제할 수 있도록합니다. 이것은 분명히 가장자리 집합이 줄어들뿐만 아니라 성장할 때만 중요합니다. 모서리에 대한 벡터를 사용하면 모든 개별 연산에 O (k)가 필요할 수 있습니다. 여기서 k는 입사 에지 수입니다.

주의 : 인접 목록의 가장자리 인 이 응용 프로그램에서 중요하지 않은 경우 벡터로 O (1) 삭제를 쉽게 얻을 수 있습니다. 마지막 요소를 삭제할 위치로 복사 한 다음 마지막 요소를 삭제하십시오! 아아, 인접성의 순서가 중요 할 때 많은 경우 (예 : 비행기에 임베딩하는 것이 걱정되는 경우)가 있습니다.

오더를 유지해야하는 경우에도 많은 작업에 대해 작업 당 평균 O (1)로 비용을 상각하도록 복사 비용을 조정할 수 있습니다. 여전히 일부 응용 프로그램에서는 이것이 충분하지 않으며 표시된 삭제 수가 코드의 고정 된 부분 일 때만 압축이 수행되는 "삭제됨"표시 (예약 된 정점 번호로 충분)가 필요합니다. 코드가 지루하고 모든 작업에서 삭제 된 노드를 확인하면 오버 헤드가 추가됩니다.

또 다른 차이점은 오버 헤드 공간입니다. 인접 목록 노드는 매우 작습니다. 단지 노드 번호입니다. 이중 링크는 숫자 자체의 공간의 4 배가 필요할 수 있습니다 (숫자가 32 비트이고 두 포인터가 모두 64 인 경우). 매우 큰 그래프의 경우 400 %의 공간 오버 헤드가 그리 좋지 않습니다.

마지막으로 긴 기간 동안 자주 편집되는 링크 된 데이터 구조는 쉽게 매우 인접하지 않은 메모리 액세스로 이어질 수 있습니다. 이렇게하면 벡터를 통한 선형 액세스에 비해 캐시 성능이 저하됩니다. 그래서 여기 벡터가 이깁니다.

대부분의 응용 프로그램에서 차이점은 걱정할 가치가 없습니다. 그리고 거대한 그래프가 현대 세계의 길입니다.

다른 사람들도 말했듯이, 연결된 노드 나 노드의 벡터로 신속하게 구현 될 수있는 인접성을 위해 일반화 된 List 컨테이너를 사용하는 것이 좋습니다. 예 : 자바에서는 List을 사용하고/profile을 LinkedList과 ArrayList으로 구현하면 애플리케이션에 가장 적합한 것을 볼 수 있습니다. NB ArrayList은 remove에 배열을 압축합니다. 위에 설명 된 바와 같이 할부 상환은 없지만 add s 은 상각됩니다.

다른 변형이 있습니다. 매우 밀도가 높은 그래프가 있는데, 특정 레이블이있는 노드에 대해 모든 노드를 검색해야하는 경우가 자주 발생한다고 가정합니다. 그런 다음 인접성에 대해 맵을 원 하십니 다. 여기서 키는 가장자리 레이블입니다. 물론지도는 해시 또는 나무 또는 skiplists 또는 당신이 좋아하는 것이어야합니다.

목록이 계속됩니다. 효율적으로 구현하는 방법 정점 삭제? 예상 할 수 있듯이 여기에도 각각 장점과 단점이있는 대안이 있습니다.