[알고리즘]그래프를 알아보자

알고리즘 스터디 중 DFS를 공부하다 그래프에 대해 제대로 된 개념이 탑재된것 같지 않아 블로그를 남겨 보려 한다.

그래프
1. 용어
  - 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 두 개의 정점을 연결한다.
  - 간선에 방향이 있으면 방향그래프, 방향이 없으면 무방향 그래프라 한다.
  - 정점 a와 b를 연결하는 간선을 (a,b)로 표현하고, 방향이 있는 경우 <a,b>로 표현한다.
  - 정점 a에 인접한 정점의 수를 a의 '차수'라고 정의한다.
  - 방향그래프에서는 차수를 진입차수, 진출차수로 구분한다.
  - 시작 정점과 도착점이 동일한 단순경로를 싸이클이라고 한다.
  - 그래프에서 정점들이 서로 연결되어 있는 부분을 연결성분(Component)라 한다.
  - (a,b,c), (e,f) 이렇게 연결성분은 2개가 있는 것이다.
  - 가중치 그래프는 간선에 가중치가 부여된 그래프다.

2. 그래프 자료구조
  - 그래프를 자료구조로 저장하기 위한 방법은 '인접행렬'과 '인접리스트' 두 가지가 있다.
  - n개의 정점을 가진 그래프의 인접행렬은 2차원 nxn 배열로 저장한다.
  - 인접행렬에서 정점 i와 j사이에 간선이 없으면 a[i][j]=0, 있으면 1로 표현한다.
  - 인접리스트는 각 정점마다 한 개의 연결리스트를 이용해 인접한 각 정점을 노드에 저장한다.

그래프에 관한 간단하게 정리 해 보았다. 다음 DFS 공부하고 블로그를 남기도록 하겠다.
끝~!!