그래프의 정의

그래프는 정점(Vertex)와 간선(Edge)로 이루어진 자료구조이다.
그래프는 대표적인 비선형 자료구조이다.

비선형 자료구조란?

비선형 자료구조는 데이터 원소 간의 관계가 순차적이 아닌
계층적 이거나 복잡한 연결 관계를 가지는 자료구조이다.

특징

요소들이 일렬로 정렬되어있지 않다.
한 요소가 여러 요소와 연결 될 수 있다.
복잡한 관계를 표현하기 좋다.

대표적인 비선형 자료구조

트리,그래프

그래프의 요소

Vertex (정점) : 데이터를 담는 단위
Edge (간선) : 정점 간의 연결
Weight (가중치) : 간선에 부여된 값
Direction (방향성) :간선에 방향이 있는 경우(유향 그래프), 없는 경우(무향 그래프)
Degree (차수) : 한 정점에 연결된 간선의 개수
Adjacency (인접) : 두 정점이 간선으로 연결되어 있는 관계
Path (경로) : 한 정점에서 다른 정점으로 가는 간선의 연속
Cycle (사이클) : 시작 정점으로 되돌아오는 경로
Connected Graph : 모든 정점이 연결되어 있는 그래프

그래프 구현

인접 리스트

인접 행렬

그래프의 종류

무방향 그래프

특징 : 간선에 방향이 없음, A-B, B-A

방향 그래프

특징 : 간선에 방향이 있음, A->B랑 B<-A는 다름

연결 그래프

특징 : 모든 정점이 경로를 통해 연결되어 있음

비연결 그래프

특징 : 일부 정점들이 서로 연결되어 있지 않음

가중치 그래프

특징 : 간선에 비용, 거리 등의 값(가중치)이 있음

순환 그래프

특징 : 정점을 따라 이동했을 때 다시 처음 위치로 돌아오는 경로가 존재함

비순환 그래프

특징 : 순환이 없음

완전 그래프

특징 : 모든 정점이 서로 연결됨