Graph

노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조.

연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조.

그래프(Graph) 용어

• 정점(vertex):
  • 위치라는 개념. (node 라고도 부름)

• 간선(edge):
  • 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)

• 인접(Adjacency) 
  • 정점 x와 정점 y가 간선에 의해 연결되어져 있다면, 이들 두 정점 x와 y를 인접(Adjacent)되어있다고 한다.

• 인접 정점(adjacent vertex):
  • 간선에 의 해 직접 연결된 정점

• 부속(Incident)
  • 정점 사이에 연결된 간선을 두 정점 X와 Y에 부속되어있다고 한다.

• 정점의 차수(degree):
  • 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배

• 진입 차수(in-degree):
  • 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)

• 진출 차수(out-degree):
  • 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)

• 경로 길이(path length):
  • 경로를 구성하는 데 사용된 간선의 수

• 단순 경로(simple path):
  • 경로 중에서 반복되는 정점이 없는 경우

• 사이클(cycle):
  • 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프(Graph)의 특징

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

• 2개 이상의 경로가 가능하다.
  • 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.

• self-loop 뿐 아니라 loop/circuit 모두 가능하다.

• 루트 노드라는 개념이 없다.

• 부모-자식 관계라는 개념이 없다.

• 순회는 DFS나 BFS로 이루어진다.

• 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.

• 그래프는 크게 방향 그래프와 무방향 그래프가 있다.

• 간선의 유무는 그래프에 따라 다르다.

그래프(Graph)의 탐색

• 깊이 우선 탐색(DFS, Depth-First Search)
  • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
  • 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
  • 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다. 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.

• 너비 우선 탐색(BFS, Breadth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
  • 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
  • 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
  • Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
  • 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  • 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색