ljjk159   4년 전

현재 메모리 초과가 뜨는 상황인데

그래프의 간선 수가 최대 10e9개까지 생길 수 있는데

메모리 초과를 피하면서 그래프를 저장할 수 있는 방법이 있는지 궁금합니다.

(현재는 인접 행렬로 그래프를 저장하고 있고, 중복되는 간선이 생기지 않도록 C++ STL set를 이용하여 인접한 정점들을 저장했습니다.)

아니면 트리와 같이 모든 간선을 저장하지 않는 방식으로 풀 수 있는 문제인가요?

코드도 함께 첨부할께요!

sait2000   4년 전

튜브를 정점으로 하고 역을 간선으로 해야 하지 않나요

sait2000   4년 전

음 굳이 안 그래도 할 수 있을 것 같기도 하네요

sait2000   4년 전

역이랑 튜브를 다 정점으로 두면 될 것 같아요

ljjk159   4년 전

역을 정점으로 하고 있었는데 튜브를 정점으로 하면 그래프가 더 간결하게 표현될 수 있겠네요..

답변 감사드립니다!!

혹시 마지막 답변에서 역이랑 튜브를 다 정점으로 둔다고 하셨는데, 그게 무슨 의미인지 자세히 알 수 있을까요?

chw0501   4년 전

1~n 정점을 역으로 두고

(n+1)~(n+m)정점을 하이퍼튜브로 두고

역이 하이퍼튜브에 속해있으면 두 정점간에 연결을 해요.

그럼 두 역 사이 이동을 간선 두개를 통해(하이퍼튜브를 타고) 이동하는 듯한 간선이 되네요.

n=1일 때 조심하셔야 돼요

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