그래프
비선형(non-linear) 자료구조이며 노드(node)와 엣지(edge)로 구성
- 노드는 꼭짓점(vertex)으로 표현됩니다
- 엣지는 두 노드를 연결하는 선(line)으로 표현됩니다.
표현
위 그래프를
Vertex) = {0, 1, 2, 3, 4}
E(edges) = {01, 12, 23, 34, 04, 14, 13}으로 표현할 수 있다.
그래프의 표현그래프를 인접 행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 표현할 수 있다.
인접 행렬
정점의 개수를 V라고 했을 때, V * V 크기의 이차원 배열을 이용한다.
A[i][j] = 1 (i -> j 간선이 있을 때), 0(없을 때)
방향 없는 그래프일 경우 i-j 연결 되어있으면
i->j / j->i 둘다 넣어주기
가중치가 있다면 행렬에 1 대신 가중치 저장하기
인접 리스트
A[i] = j k (i는 k, k와 연결됨)
리스트는 크기를 동적으로 변경할 수 있어야 하므로 링크드리스트나 길이를 동적으로 변경할 수 있는 배열을 사용한다. (cpp는 벡터를 이용할 수 있다.)
가중치가 있다면 가중치도 같이 저장한다.
