자료구조 - Graph

Graph

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

• 정점(vertex)과 간선(edge)로 구성

• 직접적인 관계: 두 점 사이를 선으로 연결

• 간접적인 관계: 몇개의 점과 선에 걸쳐 연결
  ex) 포털사이트 검색엔진, SNS 관계망, 네비게이션 등

• 비가중치 그래프: 연결 이외의 추가적인 정보를 알 수 없다

• 가중치 그래프: 연결과 더불어 추가적인 정보를 제공
  ex) 서울과 부산간의 네비게이션(단순 연결은 비가중치 / 거리, 걸리는 시간 등을 추가하면 가중치)

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge): 정점 간의 관계
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
• 무(방)향 그래프 (undirected graph): 단방향 그래프(일방통행 등)
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현

인접 리스트 & 인접 행렬

• 인접 리스트
  • 각 정점이 어떤 정점과 인접하는지 리스트 형태로 표현
  • 메모리를 효율적으로 사용하고 싶을 때 사용
• 인접 행렬
  • 서로 다른 정점들이 인접한 상태인지를 표시한 행렬. 2차원 배열의 형태로 나타냄
  • 가장 빠른 경로를 찾을 때 주로 사용
  • 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
  • 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지