Multigraph에 가장 적합한 구현은 무엇입니까?

Question

정점보다 에지가 많은 멀티 그래프를 구현하는 가장 좋은 방법은 공간 및 운영 비용입니다.

최악의 경우 5000 개의 가장자리와 1000 개의 정점이 있습니다. add edges, check adjacency between edges, add vertices (거의 항상) 등 대부분의 작업에 좋은 시간이 있기 때문에 인접 목록을 생각하고 있었지만 여전히 |v^2|의 공간을 소비합니다.

올바른 경로에 있습니까? 더 나은 구현이 있습니까? 인접성 목록을 구현하는 가장 좋은 방법에 대한 팁은 무엇입니까?

Answer 1

비율이 E/V = 5 인 것은 매우 희소 한 그래프를 의미합니다. 이는 목록에 대한 플러스입니다. 일반적으로 인접성 목록은 인접성 행렬보다 전반적으로 좋습니다.

이제 삽입 비용은 O(degree(vertex))이지만 가장자리가 거의 없으므로 무시해도됩니다. 더 이상 보지 마십시오. 인접 목록을 사용하십시오.