인접 행렬로 표시된 그래프 크기 조정

Question

"인접 행렬"표현을 사용하여 그래프를 나타 내기로 결정한 경우 행렬의 크기를 어떻게 알 수 있습니까?

내가 본 모든 코드 예제는 행렬을 초기화하기 위해 Graph 객체에 크기가 주어진다고 가정하지만이 크기의 출처는 분명하지 않습니다.
그래프를 작성하기 위해 그래프의 데이터가로드 된 것으로 가정합니다. 파일에서 가장 좋은 방법은 파일을 읽을 때 그래프를 작성하는 것입니다 (지금까지?).
이것은 목록 인 대체 표현을 사용하면 매우 쉽습니다.
그러나 matrix의 경우 파일이 실제로로드 될 때까지 정점 수를 알 수 없습니다. 나는 우리가 처음으로 파일 (수백만 개의 버텍스를 포함 할 수 있음)을 읽었으며 다음에 그래프를 작성한다고는 생각하지 않는다. 그것은 나에게 이중 처리를하는 것처럼 보입니다.

그래서 평소/가장 좋은 방법은 무엇입니까?

참고 : 내가 대신 목록을 사용의 이점을 알고 있지만, 대부분의 문서가 나는 프로그램이 matrix를 사용하는 방법을 이해하는 것을 시도하고있다 (그러나 스파 스에 대한) 밀도 그래프에, 매트릭스를 사용하는 것은 받아 들일 수 있다고 말하고 있기 때문에 표현이 올바르게 구현됩니다.

Answer 1

정점 개수가없는 경우 상용구 번호가있는 행렬 만 초기화 할 수 있다고 생각합니다. 입력 파일에 x y z 형태의 줄만 포함되어 있다고 가정하면, x에서 y까지의 가장자리가 있고 (선택 사항) 비용은 z입니다. 파일에 아무것도 포함되어 있지 않다는 가정하에 입력 파일의 행 수는 그래프의 가장자리 수입니다. 이미 빽빽한 그래프라고 가정 했으므로, n(n-1)/2과 같은 수의 가장자리를 가진 완전한 그래프라고 가정합니다. 여기서 n은 정점의 수입니다. 이 정보를 사용하여 정점의 수를 가깝게 근사시킬 수 있습니다. 예를 들어, 입력 파일의 엣지 수가 1000000이면 방정식 n*(n-1)/2 = 1000000을 풀면 1415과 거의 같은 n에 도달합니다. 행렬을 1415*1415 배열로 초기화하면 잘 처리됩니다.

물론이 모든 것은 입력 파일에서 줄 수를 읽을 수있는 충분한 방법을 가지고 있다는 사실에 기반합니다.

Answer 2

입력 형식이 사용자의 통제하에있는 경우 크기를 잘 예측할 수 있습니다. 아래 예제에서 모든 값은 고정 길이 (6 문자)로 왼쪽에 0 패딩이 있습니다. 즉, 각 줄의 크기는 22 바이트입니다. 파일 크기를 22로 나눌 때 행렬 크기의 근사값을 얻습니다. 그래프가 완료하면 파일 크기는 nxn이고, n은 정점의 수입니다.

예 :

000001 000020 000030 
000800 000001 000040 
     etc... 

다른 해결책은 크기가 초과 될 때마다 행렬의 크기를 두 배로하는 것이다. 상각 된 계산 비용은 적을 것입니다. 반면에 기억은 문제가 될 수 있습니다.

Answer 3

평소/가장 좋은 방법은 의견에 주어집니다 : 재 할당하고 복사하십시오. 크기를 매번 (예 : double) 크기를 조정하면 상환 된 (평균) 비용이 O (n)으로 나옵니다. 기억하는 한. 예를 들어, 파이썬에는 필요한 크기로 커지는 목록이 있습니다. 그것은 완전히 표준/공통입니다.

[여기에 점수를 게시하는 것은 아닙니다. 코멘트에있는 답변이 당신이 필요로하는 것이지만, 당신이 그들에게 관심을 기울이지 않거나 이해하지 못한다는 것을 좌절 시켰습니다.]