가중치가 적용된 단방향 그래프의 정점 표현

Question

가중치가 적용된 단방향 큰 그래프의 모든 정점을 나타내는 데 인접 행렬을 사용하고 있습니다. 이 그래프에서 에지는 정점을 자체에 연결하지 않습니다. 이는 내 인접 행렬의 모든 대각선 요소를 null으로 만듭니다. 내 그래프가 크면 인접 행렬에서 왼쪽 삼각형의 요소를 저장할 필요가 없습니다. 다음은 인접 행렬이있는 작은 샘플 그래프입니다.

단방향 그래프에서 왼쪽 삼각형은 직각 삼각형의 거울 이미지입니다. 즉 adjacency_matrix[i][j], adjacency_matrix[j][i]이 동일합니다. 그래서 왜 왼쪽 삼각형을 저장해야합니다. 큰 그래프의 경우이 트릭은 많은 메모리를 절약 할 수 있습니다. 동시에 에지가 꼭지점을 자체에 연결하지 않으므로 대각 요소도 0입니다. 즉 adjacency_matrix[i][i]은 0입니다. 하지만 어떻게 구현할 수 있습니까? 여기서 2D 배열을 사용할 수 있습니까?

Answer 1

자바 2D 배열이 정말하지 않습니다 :) 주요 요점을 파악해야한다.

는

당신은 아마 원하는 : 당신이 원하는 삼각형을 할당합니다

int[][] weight = new int[N][]; 
for (int i = 0; i < N; i++) weight[i] = new int[N-1-i]; 

. 그런 다음 weight [r] [c-r-1]의 행 r, col c를 색인화하십시오.

다른 옵션은 조금 더 복잡하게 계산할 수있다

int[] weight = new int[N*(N-1)/2]; 

인덱싱으로 단일 어레이를 사용하지만, 더 적은 오버 헤드 할당 포인터.

Answer 2

지그재그 배열을 사용할 수 있습니다.

int[][] matrix = new int[N][]; 
for (int i = 1; i <= N; i++) { 
    matrix[i] = new int[N - i + 1]; 
    for (int j = 1; j <= N - i + 1; j++) 
     matrix[i][j] = edgeValue; 
} 

기본적으로 각 행마다 필요한만큼 할당합니다.

P.S 어쩌면 내가 여기에 몇 가지 경계를 엉망하지만 배열의 배열을 할당 syntatic 설탕이 있지만, 당신은 여전히,