그래프의 표현

에지 리스트

에지를 중심으로 그래프를 표현하며, 리스트에 출발 노드, 도착 노드, 가중치를 저장하여 표현한다.

가중치 없는 그래프 표현

리스트의 열 2개로 출발 노드, 도착 노드만 표현

• 방향이 없는 그래프일 때 1과 2가 연결돼있을 경우, [1,2], [2,1]를 리스트에 모두 넣으면 됌

가중치 있는 그래프 표현

가중치 없는 그래프의 표현에서 행을 하나 늘려주면 됌

인접 행렬

2차원 배열을 자료구조로 이용해 그래프를 표현

가중치 없는 그래프 표현

1에서 2를 향하는 에지가 있을 경우 1행 2열에 1을 저장하는 방식으로 표현

가중치 있는 그래프 표현

가중치가 없는 그래프 표현에서 1을 넣는 자리에 가중치를 넣어주면 됌

인접 리스트(가장 중요)

노드 개수만큼 리스트를 선언

가중치 없는 그래프

n번 노드와 연결돼 있는 노드를 리스트의 index n에 연결된 노드 개수만큼 리스트에 append

가중치 있는 그래프

input data를 2개로 사용
아래 그림과 같이 A[1]에 [(2,8), (3,3)]을 연결하는 방식