1. 그래프

자료구조 - 선형 / 비선형

선형 - 자료를 저장하고 꺼내는 것에 초점 - 리스트, 딕셔너리 등

비선형 - 표현에 초점

그래프 → 연결 구조에 초점 (관계망 등)

1. 노드(Node) - 연결 관계를 가진 각 데이터 - ‘정점’(Vertex)라고도 함.
2. 간선(Edge) - 노드 간의 관계를 표시한 선.
3. 인접 노드(Adjacent Node) - 간선으로 직접 연결된 노드 (1촌 관계) - 자신은 인접 아님.

• 그래프의 종류

  • 유방향 그래프 (Directed graph)
    • 간선에 방향이 있는 그래프 (일방향) - 팔로우 관계
  • 무방향 그래프 (Undirected graph)
    • 간선에 방향이 없는 그래프 (양방향?) - 우리는 친구입니다.

• 그래프의 표현 방법

  • 인접 행렬 (Adjacent Matrix)
    • 2차원 배열로 그래프의 연결 관계를 표현
  • 인접 리스트 (Adjacent List) - 주로 씀!
    • 딕셔너리 - 리스트(python) 또는 링크드 리스트로 연결 관계를 표현

• 인접 행렬 (그림 1)

  • 공간 복잡도가 높음
  • 탐색 비용이 상수 O(1) - ex) 0, 1

< 그림 1 >

• 인접 리스트 (그림 2)
  • 공간 복잡도가 낮음 (메모리)
  • 탐색 비용이 O(n) - 해시 테이블과 마찬가지