[자료구조] 그래프와 인접 행렬, 인접 리스트

인접 행렬과 인접 리스트는 언제 사용하나요?

인접 행렬과 인접 리스트는 데이터간 연결관계를 확인할 때 사용한다.

인접하다 = 노드가 서로 엣지로 연결되어 있다.

인접 행렬 이란?

노드(데이터)들의 연결관계를 보여주는 2차원 리스트(행렬).

각 노드에 고유한 인덱스를 부여하여 연결관계를 확인한다.

행렬의 행과 열에 인덱스들을 위치 시키고, 행렬의 성분으로 인덱스간의 연결 관계를 넣는다.

 

비가중치  & 무방향 그래프인 경우 

성분이 0, 1 중 하나가 된다. 노드간 연결이 되어있으면 1, 없으면 0 이 된다.

행렬에서 왼쪽에서 오른쪽으로 내려가는 방향의 대각선을 기준으로 행렬이 좌우 대칭을 이룬다.

비가중치 & 방향 그래프인 경우 

성분이 0, 1 중 하나가 된다. 노드간 연결이 되어있으면 1, 없으면 0 이 된다.

한쪽 노드에서 다른 노드로 간선이 향하지만, 그 반대인 경우는 없으므로 행렬이 좌우 대칭을 이루지 않는다.

가중치 그래프인 경우 

행렬의 성분으로 가중치 값을 넣는다.

인접 리스트란?

리스트 : 순서를 가지고 있는 자료형

각 노드와 인접한 노드를 리스트의 형태로 담아서 표현하는 리스트.

연결되지 않은 정보도 저장하는 인접 행렬과 달리 연결 정보만 저장하고 있으므로 메모리를 효율적으로 사용할 수 있다.