인접성 매트릭스 또는 목록을 사용하는 그래프의 최소 크기

Question

나는 클래스의 그래프에 대해 배우 았으며 이제 막 인접성 매트릭스 구조 및 인접성 목록 구조를 살펴 보았습니다.

나는 목록 또는 매트릭스 구조를 추천 우리에게 필요한이 질문에 대해 조금 혼란 스러워요 :

그래프는 10,000 정점과 20,000,000 가장자리를 가지고 있으며,이 같은 작은 공간을 사용하는 것이 중요 입니다 가능한 한. 어떤 구조를 권하고 싶습니까?

내 대답은 인접 매트릭스가 적은 공간을 사용한다는 것이 었습니다. 인접리스트가 j + k 공백을 사용하고 adjacency 행렬이 j 공백을 사용하고, 여기서 j는 정점의 수이고 k는 그래프의 모서리 수를 사용합니다. 이전 수식을 사용하여 행렬이 더 작은 숫자를 찾았습니다.

그러나, 대답은 일반적으로

것 같았다, 두 구조는이 경우 잘 작동합니다. 공간 요구 사항과 관련하여 확실한 승자는 없습니다.

누군가 답변을 드릴까요?

Answer 1

아니요. 아니요. 인접성 목록 표시를 선택하십시오. 모서리가 정점의 제곱보다 훨씬 작습니다. 그렇지 않으면 인접 행렬 표현을 선택하십시오. 내 대답이 만족스럽지 않으면 책을 체크하십시오 - 알고리즘에 대한 소개 Cormen