그래프 개념

참고: 인프런 이재규님 강의

그래프란, 정점과 간선으로 이루어진 객체간의 연결 상태를 표현하는 방법을 의미한다.

정점과 간선의 절대적인 위치는 중요하지 않고 오직 연결 상태만이 중요하다는 특징이 있다. 즉, 위상적인 표현 방법이다.

위상적 : 좀 추상적인 개념이다. 절대적인 위치보다 객체간의 상대적인 위치와 상태가 중요하다는 의미로 이해하면 된다.

경로 : 말 그대로 정점 v1에서 v2로 가는 경로의 모든 순서 집합

단순 경로 : 같은 정점을 2번 지나지 않는 경로

부분 그래프 : 그래프 a가 그래프 b의 교집합이라면 a를 b의 부분 그래프라고 한다.

싸이클(회로) : 시작과 끝 정점이 같은 경로

신장트리 : 회로가 없는 그래프

완전 그래프 : 모든 정점이 간선으로 이어져있는 그래프. 정점의 갯수가 v개 일 때, 간선의 갯수가 v(v-1)/2개

밀집 그래프 : 정점보다 간선이 많은 그래프

희소 그래프 : 정점보다 간선이 적은 갯수

방향 그래프 : 간선에 방향성이 추가된 그래프 -> 일반적인 그래프는 정점사이에 간선이 있다면 양쪽으로 자유롭게 이동이 가능하지만 간선에 방향성이 있다면 정해진 방향으로만 이동이 가능하다.

+ 외차수 : 특정 정점에서 나가는 간선의 수

+ 내차수 : 특정 정점으로 들어가는 간선의 수

가중 그래프 : 말 그대로 간선마다 가치를 부여한 그래프이다. 예를 들면 공항 a 에서 b로 가는데 2시간이 걸리고 b에서 c로가는데 5시간이 걸리면 해당 가치를 간선에 부여하는 식이다.

네트워크 : 방향 그래프와 가중그래프를 합친 개념이다.

방향그래프와 가중그래프, 네트워크는 그래프를 구현하고 알고리즘을 짤 떄 중요한 개념이기 때문에 꼭 알아두어야함.

ps++

C로 배우는 알고리즘을 보고 처음 공부를 시작했었는데 그 책의 저자분이 직접하시는 강의를 들으니 기분이 묘오하다 ㅋㅋ..