Summary

• Graph(그래프) - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.

유향 그래프, 무향 그래프 - 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.

무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다.

유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.

그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.

인접 행렬

• 그래프의 연결 관계를 이차원 배열로 나타내는 방식.

ex) 인접 행렬 adj[][]라 한다면,

adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

인접 리스트

• 그래프의 연결 관계를 인덱스 + 배열로 나타내는 방식. 노드 번호가 직접적으로 저장됨.

ex) 인접 리스트 adj[]라 한다면,

adj[1] = {2, 3, 4} : 노드 1에서 갈 수 있는 노드는 2, 3, 4 이다.