Graph

Graph

• 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조를 의미한다.

• 즉, 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다.

  • ex) 지도, 지하철 노선도, 전기 회로의 소자 등등

• 그래프는 인접리스트, 인접 행렬로 구현하는 방식이 있다.

• 인접리스트

  • 인접리스트 방식은 정점들의 인접한 정점을 리스트로 표시한 것이다.

  • 배열 혹은 연결리스트를 이용해 표현한다.

  • 정점의 번호만 알면 배열의 인덱스를 통해 정점의 리스트에 쉽게 접근이 가능하다.

• 인접행렬

  • 인접 행렬은 N X N boolean 행렬을 사용하여 표현한다.

  • 인접한 정점이라면 true로 아니라면 false로 저장하여 사용한다.

  • 간선의 수와는 무관하게 N²개의 메모리 공간을 필요로 한다.

  • 두 정점을 연결하는 간선의 유무를 즉시 알아낼 수 있다.