그래프란?

• 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조
• 그래프는 연결관계에 초점을 둔다.

그래프에서 사용되는 용어

• 노드(Node) : 연결관계를 가진 각 데이터를 의미
• 간선(Edge) : 노드간의 관계를 표시한 선
• 인접노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점)

유방향 그래프

• 방향이 있는 간선을 갖는다.
• 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.

무방향 그래프

• 방향이 없는 간선

그래프를 표현하는 방법 2가지

1) 인접 행렬(Adjacency Matrix)
2) 인접 리스트(Adjacency list)

인접 행렬과 인접 리스트의 차이

시간과 공간의 차이다.
인접 행렬도 표현하면 모든 조합의 연결 여부를 저장 O(노드^2) 만큼의 공간을 사용한다.
인접 리스트로 표현하면 연결 여부를 알기위해 최대 O(간선) 만큼의 시간을 사용한다.
단,모든 조합연결 여부를 저장하지는 않기 때문에 O(노드 + 간선) 만큼의 공간을 사용한다.