인접 리스트와 그래프의 행렬 표현

겉모습은 달라도 다들 그래프의 종류 비슷한 방식으로 표현될 수 있습니다. 일반적으로 그래프 표현에는 두 가지 유형이 있습니다.

  1. 인접 매트릭스
  2. 인접 목록

인접 목록

인접리스트(Adjacency List)는 연결리스트(Linked List)로 구성됩니다. 각 정점은 배열 인덱스로 간주되며 각 요소는 연결된 목록을 나타냅니다. 이러한 연결된 목록에는 인덱스 꼭지점과 가장자리가 있는 꼭지점이 포함되어 있습니다.

인접 목록의 예는 다음과 같습니다.

인접 목록

그래프에 V개의 정점과 E개의 모서리가 포함되어 있다고 가정해 보겠습니다.

일반적으로 공간 복잡도는 다음과 같습니다. O(V + E).

최악의 경우 공간 복잡도는 다음과 같습니다. O(V2) 주어진 그래프가 완전한 그래프인 경우

인접 매트릭스

인접 매트릭스는 2차원 배열로 구성됩니다. V개의 꼭지점을 갖는 그래프, 행렬의 크기는 다음과 같습니다. VxV.

말하다, matrix[i][j] = 5. 이는 노드 i와 j 사이에 가중치가 5인 가장자리가 있음을 의미합니다.

다음 그래프와 인접 행렬을 살펴보겠습니다.

인접 매트릭스

우리는 2D 배열 다음 단계를 사용하여:

단계 1) 정점 A는 B와의 직접적인 가장자리를 가지며 가중치는 5입니다. 따라서 행 A와 열 B의 셀은 5로 채워집니다. 행 A의 나머지 셀은 XNUMX으로 채워집니다.

단계 2) 정점 B는 C와 직접 간선을 가지며 가중치는 4입니다. 따라서 행 B와 열 C의 셀은 4로 채워집니다. 행 B의 나머지 셀은 B에 나가는 가장자리가 없으므로 XNUMX으로 채워집니다. 다른 노드.

단계 3) 정점 C에는 다른 정점과의 직접적인 가장자리가 없습니다. 따라서 C행은 XNUMX으로 채워집니다.

단계 4) 정점 D에는 A와 C의 방향이 있는 가장자리가 있습니다.

  • 여기서 D행과 A열에 있는 셀의 값은 7입니다. D행과 C열에 있는 셀의 값은 2입니다.
  • D행의 나머지 셀은 XNUMX으로 채워집니다.

단계 5) 정점 E는 B와 D와의 방향이 있는 가장자리를 갖습니다. 행 E와 열 B에 있는 셀의 값은 6입니다. 행 E와 열 D에 있는 셀의 값은 3입니다. 행 D에 있는 나머지 셀은 다음과 같습니다. XNUMX으로 채워져 있습니다.

주의할 점은 다음과 같습니다.

  • 인접 행렬의 주 대각선이 0인 경우 그래프에는 자체 루프가 없습니다.
  • 그래프는 인덱스 (a, b)와 (b, a)가 같은 값을 가지지 않으면 방향 그래프입니다. 그렇지 않으면 그래프는 방향 그래프입니다.
  • 그래프는 셀 값이 1보다 큰 경우 가중치 그래프가 됩니다.

인접 행렬에는 제곱된 공간이 필요하므로 몇 가지 문제가 있습니다. 여기서는 연결되지 않은 가장자리를 저장합니다. 이러한 에지는 메모리에 공간을 할당합니다.

예를 들어, 100개의 노드가 있는 그래프가 있는 경우 이를 저장하려면 10개의 셀이 필요합니다. . 그래프에 에지가 적으면 이렇게 큰 메모리를 할당하는 것은 낭비일 수 있습니다. 따라서 인접 행렬을 사용하는 공간 복잡도는 다음과 같습니다. O(N2), 여기서 N은 그래프의 노드 수를 의미합니다.