그래프가 다양한 변형으로 분류될 수 있다는 것을 알고 있습니다. 그것들은 지시되거나 지시되지 않을 수 있으며 가중치가 있거나 가중치가 없을 수 있습니다. 여기서는 가중 그래프를 메모리에 표시하는 방법을 살펴보겠습니다. 다음 그래프를 고려하십시오 -
인접 행렬 표현
인접행렬 형식을 사용하여 가중치 그래프를 저장하기 위해 행렬을 비용행렬이라고 합니다. 여기서 M[i, j] 위치의 각 셀은 가장자리 i에서 j까지 가중치를 유지합니다. 가장자리가 없으면 무한대가 됩니다. 동일한 노드의 경우 0이 됩니다.
| 0 | ∞ | 6 | 3 | ∞ |
| 3 | 0 | ∞ | ∞ | ∞ |
| ∞ | ∞ | 0 | 2 | ∞ |
| ∞ | 1 | 1 | 0 | ∞ |
| ∞ | 4 | ∞ | 2 | 0 |
인접 목록 표현
인접 목록에서 목록의 각 요소에는 두 개의 값이 있습니다. 첫 번째는 대상 노드이고 두 번째는 이 두 노드 사이의 가중치입니다. 표현은 아래와 같습니다.
