[자료구조] 그래프(Graph) 표현 | 인접 행렬, 인접 리스트, 인접 배열

그래프(Graph) 표현

그래프의 표현 방법에는 인접 행렬, 인접 리스트, 인접 배열이 존재합니다.

 

인접 행렬(adjacency matrix) 방법

간선 (i, j)가 존재하면 원소(i, j) = 1을 저장하며 그렇지 않으면 원소(i, j) = 0이 됩니다.

정점의 총 개수가 N이라고 할 때 인접 행렬은 N X N 행렬입니다.

무방향 그래프의 경우 대각선 행렬을 중심으로 대칭적이지만 방향 그래프의 경우 반드시 대칭적이지 않고 비대칭일 수도 있습니다. 

또한 가중치가 있는 그래프의 경우 원소(i, j)는 1 대신에 가중치를 저장합니다.

 

인접 리스트(adjacency list) 방법

정점의 총 개수가 N이라고 할 때 각 정점에 인접한 정점들을 N개의 연결리스트로 표현한 방법입니다.

i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓은 것입니다.

또한 가중치가 있는 그래프의 경우 리스트에 가중치도 저장합니다.

(무방향 그래프인 경우 하나의 간선 당 노드가 2개씩 생기며, 방향 그래프인 경우 하나의 간선 당 노드가 1개씩 생깁니다)

 

인접 배열(adjacency array) 방법

정점의 총 개수가 N이라고 할 때 N개의 연결 배열로 표현합니다.

i번째 배열은 정점 i에 인접한 정점들의 집합을 나타냅니다.

또한 가중치가 있는 그래프의 경우 리스트에 가중치도 저장합니다.