[자료구조] 그래프 개념

그래프란?

데이터간 연결관계를 저장하는 자료구조.

데이터 하나를 점으로 보고, 점 사이를 선으로 연결하여 데이터간 연결 관계를 나타낸다.

점은 정점(vertex) 혹은 노드(node)라고 부르고 선은 엣지(edge) 혹은 간선이라고 부른다.

두 데이터가 직접적인 관계를 가지고 있으면, 서로 선으로 연결해주며

여러개의 점과 선으로 연결되어있는 데이터는 서로 간접적인 관계를 가지고 있다고 생각한다.

서로 아무런 접점/연결성이 없으면 관계가 없다고 말한다.

비가중치 그래프

가중치가 없는 그래프이다.

두 점끼리 관련이 있다는 것은 파악 할 수 있지만, 세부 정보는 알 수 없는 그래프.

(정점간의 연결 유무만 확인 가능)

가중치 : 두 점이 얼마나 관련이 있는지 알려주는 척도. 정보를 나타내는 수치

예) 사람 사이의 친밀도, 지역간의 거리

가중치 그래프

두 점끼리의 연결 상태 뿐만 아니라, 연결 상태와 관련된 정보까지 가지고 있는 그래프.

(정점 간의 연결 유무 뿐만 아니라 관련 정보들까지 확인 가능)

그래프 용어

• 노드(node)/정점(vertex) : 그래프에서 하나의 데이터
• 엣지(edge)/간선 : 데이터 간의 연결 관계
• 차수 : 하나의 노드에 연결되어 있는 엣지들의 수
• 방향 그래프 : 들어오는 간선과 나가는 간선이 존재하는 그래프. 데이터 사이에 방향성이 있는 그래프.
  • 예)A는 B를 팔로우 하지만 B는 A를 팔로우 하지 않음(A -> B)
• 무방향 그래프 : 데이터 사이에 간선이 존재하고, 방향성이 양방향인 그래프
  • 예)A와 B는 서로를 팔로우 한다(A -> B / B -> A , ∴ A - B)
• 출력 차수/진출 차수(out-degree) : 노드에서 다른 노드로 나가는 엣지들의 수
• 입력 차수/진입 차수(in-degree) : 다른 노드에서 해당 노드에 들어오는 엣지들의 수
• 경로 : 한 노드에서 다른 노드로 가는 길.
  • 다른 노드를 거치지 않고 자기 자신으로 되돌아 오는 엣지를 가지면 '자기 루프' 를 가졌다고 말한다.
  • 자기 자신에서 출발한 노드가 경로를 걸쳐 다시 자기 자신으로 돌아오는 경로를 가지면 '사이클' 이 존재한다고 한다.
• 경로의 거리
  • 비가중치 그래프 : 한 경로에 있는 엣지들의 총 수
  • 가중치 그래프 : 한 경로에 있는 엣지들이 가지는 가중치의 합
• 최단 경로 : 두 노드 사이의 경로 중 거리가 가장 짧은 경로