algospot   2년 전

댓글쓰기가 안되어 새로 질문 올려 죄송합니다. 인접행렬법으로 구현할때는 아무래도 메모리낭비가 심한 것 같은데, 그럼 인접리스트법으로 구현을 하는 것이 맞나요? 그런데 또 인접리스트로 하려하니 간선의 수게 최대 300,000개 이므로 희소그래프가 아닐 수도 있어서 아직 해보진 않았지만 에러뜰까봐 미리 질문 드려봅니다. 어떤식으로 구현을 해야 메모리제한을 받지 않을가요?

Nada   2년 전

인접행렬일 경우 사용되는 메모리는 20000 * 20000 입니다. 
하지만 인접리스트일 경우 사용되는 메로리는 300,0000입니다. 
이는 128MB보다 작은 값을 가지고 있죠.

보통 노드가 1000정도의 작은 값을 가지고 있을 때 인접 행렬을 사용하고
그 이상일 때 인접 리스트를 사용하는데 나중에는 대부분 인접 리스트를 이용해서 
Edge의 정보를 저장합니다.

baekjoon   2년 전

댓글 쓰기에 대해서는 [email protected] 메일 주세요.

사용하는 OS와 웹 브라우저 버젼을 적어 주시면, 제가 빨리 고쳐보겠습니다.

hihihi   2년 전

Nada 메로리!!

댓글을 작성하려면 로그인해야 합니다.