# Graph

## 1. Graph의 구조

* 직접적인 관계가 있는 경우, 두 점 사이를 이어주는 선이 있음
* 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐
* 하나의 점을 그래프에서는 정점(vertex)라고 표현, 하나의 선을 간선(edge)라고 함

\


## 2. Graph의 표현 방식

* 인접 행렬
  * 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 말함
  * 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄
* 인접 리스트
  * 각 정점이 어떤 정점과 인접하는지 리스트 형태로 표현

\


## 3. 알아두어야 할 Graph 용어들

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

\


## 4. BFS와 DFS

* BFS(Breadth-First Search)
  * 너비를 먼저 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 함
  * 주로 두 정점 사이의 최단 경로를 찾을 때 사용
* DFS(Depth-First Search)
  * 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용
  * BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색 가능
