Graph

Graph

• vertex와 edge로 이루어진 자료구조
• adjacent verte
  • edge에 의해 연결된 정점
• degree
  • 무방향 graph에서 하나의 정점에 인접한 정점의 수

Graph 구현 방식

• 인접행렬
  • graph를 2차원 list로 만든 방식
  • 정점이 연결되어 있으면 1 아니면 0으로 설정
  • 장점
    • 2차원 배열 안에 모든 vertex와 edge의 정보가 있기 때문에 두 vertex에 대한 연결 정보를 O(1)로 확인가능
  • 단점
    • 행렬을 만들때 $O(n^2)$가 걸림
    • 연결되지 않아도 정보를 입력하기 때문에 memory 낭비가 심함
• 인접리스트
  • graph에서 연결된 vertex들을 list로 연결해 주는 방식
  • 장점
    • 연결 정보를 탐색할때 $O(n)$이 걸림
    • 연결된 정보만 담고 있기 때문에 memory 소비가 적음.
  • 단점
    • 인접행렬 대비 두 점의 연결관계를 확인하는데 시간이 오래걸림.