자료구조 Graph

Graph이란?

Graph의 정의

그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다.
이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다.

Graph의 용어

• 정점(vertext) : 위치라는 개념
• 간선(edge) : 정점을 연결하는 선
• 인접 정점(adjacent vertex) : 간선에 직접 연결된 정점
• 차수(degree) : 한 정점에 연결된 간선의 수 (주로 무방향 그래프에서 사용)
• 입력 차수(in-degree) : 한 정점으로 들어오는 간선의 수 (주로 방향그래프에서 사용)
• 출력 차수(out-degree) : 한 정점에서 나가는 간선의 수(주로 방향그래프에서 사용)
• 사이클(cycle) : 한 정점에서 출발하여 시작했던 정점으로 돌아오는 경로
• 가중치 그래프 : 간선마다 가중치 값이 매겨져있는 그래프

Graph의 특징

• 그래프는 순환 혹은 비순환 구조를 이룬다

• 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있다.

• 루트 노드의 개념이 없다 / 부모-자식 관계라는 개념이 없다.

• 2개 이상의 경로가 가능하다.(무방향, 방향, 양방향 가능)

• 그래프는 네트워크 모델이다.

Graph의 종류

1. 무방향 그래프(Undirected Graph)
   : 간선을 통해 양방향으로 갈 수 있다.
   정점 A와 정점 B를 연결하는 간선은 (A,B), (B,A) 이다.
   
2. 방향 그래프(Directed Graph)
   : 간선에 방향성이 존재하는 그래프
   A -> B로 갈 수 있는 간선은 (A, B)로 표시한다.
   
3. 가중치 그래프(Weighted Graph)
   : 간선을 이동하는데 비용이나 가중치가 할당된 그래프
   네트워크라고도 한다.

Graph의 표현 방식

• 인접행렬
  두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기한다.
  정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다.
  
• A의 진출차수는 1개 입니다: A —> C
  [0][2] === 1
• B의 진출차수는 2개 입니다: B —> A, B —> C
  [1][0] === 1
  [1][2] === 1
• C의 진출차수는 1개입니다: C —> A
  [2][0] === 1

인접 행렬을 사용할 때
1. 한 개의 큰표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
2. 가장 빠른 경로를 찾고자 할 때 주로 사용한다.

• 인접 리스트 : 각 정점이 어떤 정점과 인접하는지를 리시트의 형태로 표현
  

인접 리스트를 사용할 때
1. 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
(인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.)